Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets
- PDF / 749,310 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 54 Downloads / 211 Views
Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets Jean-Daniel Boissonnat1 · Olivier Devillers2 · Kunal Dutta3
· Marc Glisse4
Received: 8 March 2019 / Revised: 25 May 2020 / Accepted: 15 July 2020 © The Author(s) 2020
Abstract Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms which are both simple and efficient in theory and in practice. Randomized incremental constructions are usually space-optimal and timeoptimal 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 to understand how RIC behaves when the input is nice in the sense that the associated output is significantly smaller than in the worst case. For example, it is known that the Delaunay triangulation of nicely distributed points in Ed or on polyhedral surfaces in E3 has linear complexity, as opposed to a worst-case complexity of (n d/2 ) in the first case and quadratic in the second. The standard analysis does not provide accurate bounds on the complexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the two cases above and variants of them, the complexity of the usual RIC is O(n log n), which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value. At the heart of our proof is a bound on the complexity of the Delaunay triangulation of random subsets of ε-nets. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest. Keywords Randomized incremental construction · Delaunay triangulations · Voronoi diagrams · Flat torus · Polyhedral surfaces · Probabilistic analysis Mathematics Subject Classification 52-08 · 52C45 · 52C15 · 52C17 · 68Q87
Editor in Charge: Kenneth Clarkson Extended author information available on the last page of the article
123
Discrete & Computational Geometry
1 Introduction The randomized incremental construction (RIC) is an algorithmic paradigm introduced by Clarkson and Shor [12], which has since found immense applicability in computational geometry, e.g. [27,28]. The general idea is to process the input points sequentially in a random order, and to analyze the expected complexity of the resulting procedure. The theory developed by Clarkson and Shor is quite general and led to numerous algorithms which are simple and efficient, both in theory and in practice. On the theory side, randomized incremental constructions are usually optimal in space and time in the worst case, as exemplified by the construction of convex hulls, Delaunay triangulations, and arrangements of line segments. Randomized incremental constructions are also known to perform very efficiently in practice, which, together with their simplicity, makes them the most
Data Loading...
