Randomized incremental construction of Delaunay triangulations of nice point sets

Autor: Olivier Devillers, Jean-Daniel Boissonnat, Marc Glisse, Kunal Dutta
Přispěvatelé: Understanding the Shape of Data (DATASHAPE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Geometric Algorithms and Models Beyond the Linear and Euclidean realm (GAMBLE ), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), ANR-17-CE40-0017,ASPAG,Analyse et Simulation Probabilistes des Algorithmes Géométriques(2017), ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), European Project: 339025,EC:FP7:ERC,ERC-2013-ADG,GUDHI(2014), Laboratoire Cogitamus, This work is supported by the European Research Council under Advanced Grant 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). This work has also been supported by the French government, through the ANR project ASPAG (ANR-17-CE40-0017) and the 3IA Cˆote d’Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002., INRIA
Jazyk: angličtina
Rok vydání: 2019
Předmět:
Probabilistic analysis
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0102 computer and information sciences
02 engineering and technology
Computer Science::Computational Geometry
[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
01 natural sciences
Article
Computational geometry
Theoretical Computer Science
Combinatorics
010104 statistics & probability
Line segment
Quadratic equation
Randomized incremental construction
Simple (abstract algebra)
[MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT]
0202 electrical engineering
electronic engineering
information engineering
Discrete Mathematics and Combinatorics
Probabilistic analysis of algorithms
0101 mathematics
Mathematics
average-case analysis
Theory of computation
000 Computer science
knowledge
general works
Delaunay triangulation
68Q87
Delaunay triangulations
Regular polygon
020206 networking & telecommunications
Binary logarithm
52C45
Flat torus
52C15
Computational Theory and Mathematics
52C17
010201 computation theory & mathematics
Voronoi diagrams
[MATH.MATH-AT]Mathematics [math]/Algebraic Topology [math.AT]
Computer Science
Polyhedral surfaces
020201 artificial intelligence & image processing
Geometry and Topology
Voronoi diagram
52-08
Zdroj: ESA 2019-27th Annual European Symposium on Algorithms
ESA 2019-27th Annual European Symposium on Algorithms, Sep 2019, Munich, Germany. ⟨10.4230/LIPIcs.ESA.2019.22⟩
Discrete & Computational Geometry
Discrete and Computational Geometry
Discrete and Computational Geometry, Springer Verlag, 2020, 64, pp.33. ⟨10.1007/s00454-020-00235-7⟩
[Research Report] INRIA. 2019
Discrete and Computational Geometry, 2020, 64, pp.33. ⟨10.1007/s00454-020-00235-7⟩
ISSN: 0179-5376
1432-0444
DOI: 10.4230/LIPIcs.ESA.2019.22⟩
Popis: 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 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 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 $${\mathbb {E}}^d$$ E d or on polyhedral surfaces in $${\mathbb {E}}^3$$ E 3 has linear complexity, as opposed to a worst-case complexity of $$\Theta (n^{\lfloor d/2\rfloor })$$ Θ ( 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)$$ 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 $${\varepsilon }$$ ε -nets. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.
Databáze: OpenAIRE
Externí odkaz: