Delaunay triangulation of a random sample of a good sample has linear size
Jean‐Daniel Boissonnat, Olivier Devillers, Kunal Dutta, Marc Glisse · HAL (Le Centre pour la Communication Scientifique Directe) · 2017
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.