Alladi Ramakrishnan Hall

On the Randomized Incremental Construction of Delaunay Triangulations of Epsilon-nets

Kunal Dutta

INRIA Sophia Antipolos

The randomized incremental construction (RIC) paradigm for building geometric data structures introduced by Clarkson and Shor [Disc. & Comp. Geom., 1989] has found wide application in the field of computational geometry and related areas such as graphics, statistical inference and machine learning. It has been analyzed extensively from the point of view of worst-case distributions. In many practical situations however, we 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 $\varepsilon$-nets. Under some additional assumptions, our proof works in geodesic metric spaces. A key component of our proof is a bound on the
probabilities of certain non-monotone events under sampling without replacement, which may be of general interest.

Joint work with J.-D. Boissonnat, O. Devillers and M. Glisse.