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
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download


https://hal.inria.fr/hal-01568030
Contributor : Olivier Devillers <>
Submitted on : Monday, July 24, 2017 - 5:29:29 PM
Last modification on : Friday, September 20, 2019 - 4:56:35 PM

Files

RR-9082.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

325

Files downloads

114