Delaunay triangulation of a random sample of a good sample has linear size

Description

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.

Abstract (French)

Un bon échantillon est un ensemble de points tel que toute boule de rayon $\epsilon$ contienne un nombre constant de points.Il est démontré que la triangulation de Delaunay d'un bon échantillon a une taille linéaire, malheureusement cela ne suffit pas à assurerune bonne complexité à la construction incrémentale randomisée de latriangulation de Delaunay.Dans ce rapport, nous démontrons que la triangulation d'un échantillon aléatoire de Bernoullid'un bon échantillon a une taille linéaire. Nous en déduisonsque la construction incrémentale randomisée peut être faite en temps$O(n \log n)$ et espace $O(n)$.

Additional details