Order types of random point sets can be realized with small integer coordinates

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/113414

Title:	Order types of random point sets can be realized with small integer coordinates
Author:	Fabila-Monroy, Ruy; Huemer, Clemens
Other authors:	Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
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?
Subject(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística -Computational geometry -Geometria computacional
Rights:
Document type:	Article - Published version Conference Object
Share: