Skip to Main content Skip to Navigation

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
LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry, Inria Nancy - Grand Est
2 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : A good sample is a point set such that any ball of radius $\epsilon$ contains a constant number of points. The Delaunay triangulation of a good sample is 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 random Bernoulli sample of a good sample has a triangulation of linear size. This result allows to prove that the randomized incremental construction needs an expected linear size and an expected $O(n\log n)$ time.
Document type :
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Monday, July 24, 2017 - 5:29:29 PM
Last modification on : Saturday, October 16, 2021 - 11:26:10 AM


Files produced by the author(s)


  • HAL Id : hal-01568030, version 1


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⟩



Record views


Files downloads