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

The randomized incremental construction (RIC) for building geometric data structures has been analyzed extensively, from the point of view of worst-case distributions. In many practical situations however, we have to face nicer distributions. A natural question that arises is: do the usual RIC algorithms automatically adapt when the point samples are nicely distributed. We answer positively to this question for the case of the Delaunay triangulation of ε-nets. ε-nets are a class of nice distributions in which the point set is such that any ball of radius ε contains at least one point of the net and two points of the net are distance at least ε apart. The Delaunay triangulations of ε-nets are 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 uniform random sample of a given size that is taken from an ε-net has a linear sized Delaunay triangulation in any dimension. This result allows us to prove that the randomized incremental construction needs an expected linear size and an expected O(n log n) time. Further, we also prove similar results in the case of non-Euclidean metrics, when the point distribution satisfies a certain bounded expansion property; such metrics can occur, for example, when the points are distributed on a low-dimensional manifold in a high-dimensional ambient space.