On Order Types of Random Point Sets - Université de Lorraine Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2018

On Order Types of Random Point Sets

Résumé

Let $P$ be a set of $n$ random points chosen uniformly in the unit square. In this paper, we examine the typical resolution of the order type of $P$. First, we show that with high probability, $P$ can be rounded to the grid of step $\frac{1}{n^{3+\epsilon}}$ without changing its order type. Second, we study algorithms for determining the order type of a point set in terms of the the number of coordinate bits they require to know. We give an algorithm that requires on average $4n \log 2 n + O(n)$ bits to determine the order type of $P$, and show that any algorithm requires at least $4n \log 2 n − O(n \log \log n)$ bits. Both results extend to more general models of random point sets.
Fichier principal
Vignette du fichier
depot.pdf (802.68 Ko) Télécharger le fichier
Vignette du fichier
vignette.png (156.56 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...

Dates et versions

hal-01962093 , version 1 (20-12-2018)
hal-01962093 , version 2 (28-05-2020)

Identifiants

Citer

Olivier Devillers, Philippe Duchon, Marc Glisse, Xavier Goaoc. On Order Types of Random Point Sets. 2018. ⟨hal-01962093v1⟩
393 Consultations
232 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More