Order types of random point sets can be realized with small integer coordinates
Tipus de documentText en actes de congrés
Data publicació2017
Condicions d'accésAccés obert
Tots els drets reservats. Aquesta obra està protegida pels drets de propietat intel·lectual i
industrial corresponents. Sense perjudici de les exempcions legals existents, queda prohibida la seva
reproducció, distribució, comunicació pública o transformació sense l'autorització del titular dels drets
Abstract
Let S := {p1, . . . , pn} be a set of n points chosen independently and uniformly at random from the unit square and let M be a positive integer. For every point pi = (xi , yi) in S, let p 0 i = (bMxic, bMyic). Let S 0 := {p 0 i : 1 = i = n}. We call S 0 the digitization of S by M. In this paper we study the problem: How large does M have to be such that with high probability, S and S 0 have the same order type?
CitacióFabila-Monroy, R., Huemer, C. Order types of random point sets can be realized with small integer coordinates. A: Encuentros de Geometría Computacional. "XVII Spanish Meeting on Computational Geometry: book of abstracts, Alicante, June 26-28". Alicante: 2017, p. 73-76.
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
Order types of ... ll integer coordinates.pdf | 9,453Mb | Visualitza/Obre |