#### 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.

Done