Skip to Main content Skip to Navigation
Conference papers

Randomized incremental construction of Delaunay triangulations of nice point sets

Jean-Daniel Boissonnat 1 Olivier Devillers 2 Kunal Dutta 1 Marc Glisse 1
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Randomized incremental construction(RIC) is one of the most important paradigms for buildinggeometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in theory and in practice. Randomized incremental constructions are most of the time space and time optimal in the worst-case, as exemplified by the construction of convex hulls, Delaunay triangulations and arrangements of line segments. However, the worst-case scenario occurs rarely in practice and we would like tounderstand how RIC behaves when the input is nice in the sense that the associated output issignificantly smaller than in the worst-case. For example, it is known that the Delaunay triangulations of nicely distributed points on polyhedral surfaces in $E3$ has linear complexity, as opposed to aworst-case quadratic complexity. The standard analysis does not provide accurate bounds on thecomplexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the case of nicely distributed points on polyhedral surfaces, the complexity of the usual RIC is $O(nlogn)$, which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value.Our proofs also work for some other notions of nicely distributed point sets, such as $(ε,κ)$-samples.Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Tuesday, July 16, 2019 - 4:44:38 PM
Last modification on : Friday, February 4, 2022 - 9:00:13 AM


Files produced by the author(s)



Jean-Daniel Boissonnat, Olivier Devillers, Kunal Dutta, Marc Glisse. Randomized incremental construction of Delaunay triangulations of nice point sets. ESA 2019 - 27th Annual European Symposium on Algorithms, Sep 2019, Munich, Germany. ⟨10.4230/LIPIcs.ESA.2019.22⟩. ⟨hal-02185566⟩



Record views


Files downloads