Delaunay triangulation of a random sample of a good sample has linear size

Olivier Devillers 1 Marc Glisse 2
1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
2 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Résumé : Un bon échantillon est un ensemble de points tel que toute boule de rayon $\epsilon$ contienne un nombre constant de points. Il est démontré que la triangulation de Delaunay d'un bon échantillon a une taille linéaire, malheureusement cela ne suffit pas à assurer une bonne complexité à la construction incrémentale randomisée de la triangulation de Delaunay. Dans ce rapport, nous démontrons que la triangulation d'un échantillon aléatoire de Bernoulli d'un bon échantillon a une taille linéaire. Nous en déduisons que la construction incrémentale randomisée peut être faite en temps $O(n \log n)$ et espace $O(n)$.
Type de document :
Rapport
[Research Report] RR-9082, Inria Saclay Ile de France; Inria Nancy - Grand Est. 2017, pp.6
Liste complète des métadonnées



https://hal.inria.fr/hal-01568030
Contributeur : Olivier Devillers <>
Soumis le : lundi 24 juillet 2017 - 17:29:29
Dernière modification le : lundi 31 juillet 2017 - 15:43:39

Fichiers

RR-9082.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01568030, version 1

Citation

Olivier Devillers, Marc Glisse. Delaunay triangulation of a random sample of a good sample has linear size. [Research Report] RR-9082, Inria Saclay Ile de France; Inria Nancy - Grand Est. 2017, pp.6. <hal-01568030>

Partager

Métriques

Consultations de
la notice

133

Téléchargements du document

28