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

Jean-Daniel Boissonnat 1 Olivier Devillers 2 Kunal Dutta 1 Marc Glisse 1
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : The randomized incremental construction (RIC) for building geometric data structures has been analyzed extensively, from the point of view of worst-case distributions. In many practical situations however, we have to face nicer distributions. A natural question that arises is: do the usual RIC algorithms automatically adapt when the point samples are nicely distributed. We answer positively to this question for the case of the Delaunay triangulation of ε-nets. ε-nets are a class of nice distributions in which the point set is such that any ball of radius ε contains at least one point of the net and two points of the net are distance at least ε apart. The Delaunay triangulations of ε-nets are proved to have linear size; unfortunately this is not enough to ensure a good time complexity of the randomized incremental construction of the Delaunay triangulation. In this paper, we prove that a uniform random sample of a given size that is taken from an ε-net has a linear sized Delaunay triangulation in any dimension. This result allows us to prove that the randomized incremental construction needs an expected linear size and an expected O(n log n) time. Further, we also prove similar results in the case of non-Euclidean metrics, when the point distribution satisfies a certain bounded expansion property; such metrics can occur, for example, when the points are distributed on a low-dimensional manifold in a high-dimensional ambient space.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : jeudi 28 décembre 2017 - 18:01:49
Dernière modification le : samedi 27 janvier 2018 - 01:32:13


Fichiers produits par l'(les) auteur(s)



Jean-Daniel Boissonnat, Olivier Devillers, Kunal Dutta, Marc Glisse. Delaunay triangulation of a random sample of a good sample has linear size . 2017. 〈hal-01673170〉



Consultations de la notice


Téléchargements de fichiers