Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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
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 :
Reports (Research report)
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 : Wednesday, October 26, 2022 - 8:15:07 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