LIPIcs.ISAAC.2020.28.pdf
- Filesize: 0.76 MB
- 15 pages
Document
Efficiently Computing All Delaunay Triangles Occurring over All Contiguous Subsequences
Authors
-
Part of:
Volume:
31st International Symposium on Algorithms and Computation (ISAAC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
Cite As Get BibTex
Stefan Funke and Felix Weitbrecht. Efficiently Computing All Delaunay Triangles Occurring over All Contiguous Subsequences. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.28
Abstract
Given an ordered sequence of points P = {p₁, p₂, … , p_n}, we are interested in computing T, the set of distinct triangles occurring over all Delaunay triangulations of contiguous subsequences within P. We present a deterministic algorithm for this purpose with near-optimal time complexity O(|T|log n). Additionally, we prove that for an arbitrary point set in random order, the expected number of Delaunay triangles occurring over all contiguous subsequences is Θ(nlog n).
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Computational Geometry
- Delaunay Triangulation
- Randomized Analysis
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Alok Aggarwal, Leonidas J. Guibas, James Saxe, and Peter W. Shor. A linear-time algorithm for computing the voronoi diagram of a convex polygon. Discrete & Computational Geometry, 4(6):591-604, December 1989. URL: https://doi.org/10.1007/BF02187749.
- Nina Amenta, Marshall W. Bern, and David Eppstein. The crust and the beta-skeleton: Combinatorial curve reconstruction. Graphical Models and Image Processing, 60(2):125-135, 1998. URL: https://doi.org/10.1006/gmip.1998.0465.
- Annika Bonerath, Benjamin Niedermann, and Jan-Henrik Haunert. Retrieving α-shapes and schematic polygonal approximations for sets of points within queried temporal ranges. In SIGSPATIAL/GIS, pages 249-258. ACM, 2019. URL: https://doi.org/10.1145/3347146.3359087.
- Herbert Edelsbrunner, David G. Kirkpatrick, and Raimund Seidel. On the shape of a set of points in the plane. IEEE Trans. Information Theory, 29(4):551-558, 1983. URL: https://doi.org/10.1109/TIT.1983.1056714.
- Steven Fortune. A sweepline algorithm for voronoi diagrams. Algorithmica, 2(1-4):153, 1987. URL: https://doi.org/10.1007/BF01840357.
- Leonidas Guibas and Jorge Stolfi. Primitives for the manipulation of general subdivisions and the computation of voronoi diagrams. ACM Transactions On Graphics (TOG), 4(2):74-123, 1985. URL: https://doi.org/10.1145/282918.282923.
- Leonidas J. Guibas, Donald E. Knuth, and Micha Sharir. Randomized incremental construction of delaunay and voronoi diagrams. Algorithmica, 7(1):381-413, 1992. URL: https://doi.org/10.1007/BF01758770.
- Scott Huddleston and Kurt Mehlhorn. A new data structure for representing sorted lists. Acta Informatica, 17:157-184, 1982. URL: https://doi.org/10.1007/BF00288968.
- Haim Kaplan, Edgar Ramos, and Micha Sharir. The overlay of minimization diagrams in a randomized incremental construction. Discrete & Computational Geometry, 45(3):371-382, 2011. URL: https://doi.org/10.1007/s00454-010-9324-6.
- David G. Kirkpatrick and John D. Radke. A framework for computational morphology. In Godfried Toussaint, editor, Computational Geometry, volume 2 of Machine Intelligence and Pattern Recognition, pages 217-248. North-Holland, 1985. URL: https://doi.org/10.1016/B978-0-444-87806-9.50013-X.
- Cao An Wang and Francis Chin. Finding the constrained delaunay triangulation and constrained voronoi diagram of a simple polygon in linear-time. In Paul Spirakis, editor, Algorithms - ESA '95, pages 280-294. Springer, 1995. URL: https://doi.org/10.1007/3-540-60313-1_150.