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 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 worstcase, as exemplified by the construction of convex hulls, Delaunay triangulations and arrangements of line segments. However, the worstcase 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 worstcase. For example, it is known that the Delaunay triangulations of nicely distributed points on polyhedral surfaces in E^3 has linear complexity, as opposed to a worstcase quadratic complexity. 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 case of nicely distributed points on polyhedral surfaces, 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.
Our proofs also work for some other notions of nicely distributed point sets, such as (epsilon, kappa)samples. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.
BibTeX  Entry
@InProceedings{boissonnat_et_al:LIPIcs:2019:11143,
author = {JeanDaniel Boissonnat and Olivier Devillers and Kunal Dutta and Marc Glisse},
title = {{Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {22:122:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11143},
URN = {urn:nbn:de:0030drops111437},
doi = {10.4230/LIPIcs.ESA.2019.22},
annote = {Keywords: Randomized incremental construction, Delaunay triangulations, Voronoi diagrams, polyhedral surfaces, probabilistic analysis}
}
Keywords: 

Randomized incremental construction, Delaunay triangulations, Voronoi diagrams, polyhedral surfaces, probabilistic analysis 
Collection: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 