LIPIcs.SoCG.2021.16.pdf
- Filesize: 0.69 MB
- 15 pages
Document
Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory
Authors
Ranita Biswas 
,
Sebastiano Cultrera di Montesano ,
Herbert Edelsbrunner ,
Morteza Saghafian
-
Part of:
Volume:
37th International Symposium on Computational Geometry (SoCG 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-02
File
Document Identifiers
Author Details
- IST Austria (Institute of Science and Technology Austria), Klosterneuburg, Austria
- IST Austria (Institute of Science and Technology Austria), Klosterneuburg, Austria
Cite AsGet BibTex
Ranita Biswas, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.16
https://doi.org/10.4230/LIPIcs.SoCG.2021.16
Abstract
Generalizing Lee’s inductive argument for counting the cells of higher order Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse theoretic quantities for piecewise constant functions on planar arrangements. Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for 1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s first k-1 sublevel sets. We get similar expressions for the vertices, edges, and polygons of the order-k Voronoi tessellation.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Voronoi tessellations
- Delaunay mosaics
- arrangements
- convex polytopes
- Morse theory
- counting
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Thomas Banchoff. Critical points and curvature for embedded polyhedra. Journal of Differential Geometry, 1:245-256, 1967.
-
Kenneth L. Clarkson and Peter W. Shor. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry, 4:387-421, 1989.
-
Herbert Edelsbrunner and Georg Osang. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. Journal of Geometry, 2021. (accepted).
-
Gábor Fejes Tóth. Multiple packing and covering of the plane with circles. Acta Mathematica Academiae Scientiarum Hungaricae, 27:135-140, 1976.
-
Robin Forman. Morse theory for cell complexes. Advances in Mathematics, 134(1):90-145, 1998.
-
Der-Tsai Lee. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Transactions on Computers, 31(6):478-487, 1982.
-
Ketan Mulmuley. Output sensitive construction of levels and Voronoi diagrams in R^d of order 1 to k. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC'90, pages 322-330, 1990.
-
Michael I. Shamos and Dan Hoey. Closest-point problems. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, SFCS'75, pages 151-162, 1975.
-
Micha Sharir, Shakhar Smorodinsky, and Gábor Tardos. An improved bound for k-sets in three dimensions. Discrete & Computational Geometry, 26:195-204, 2001.
-
Georges Voronoi. Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire: recherches sur les paralléloèdres primitifs. Journal für die reine und angewandte Mathematik, 134:198-287, 1908.