Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

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.
Complete list of metadata
Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Thursday, December 28, 2017 - 6:01:49 PM
Last modification on : Friday, February 4, 2022 - 9:00:13 AM


Files produced by the author(s)


  • HAL Id : hal-01673170, version 1


Jean-Daniel Boissonnat, Olivier Devillers, Kunal Dutta, Marc Glisse. Delaunay triangulation of a random sample of a good sample has linear size . {date}. ⟨hal-01673170⟩



Record views


Files downloads