2026-07-24T19:05:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13815 2024-03-06T10:52:47Z ddc:004 open_access

Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory Biswas, Ranita Cultrera di Montesano, Sebastiano Edelsbrunner, Herbert Saghafian, Morteza Voronoi tessellations Delaunay mosaics arrangements convex polytopes Morse theory counting 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ranita Biswas and Sebastiano Cultrera di Montesano and Herbert Edelsbrunner and Morteza Saghafian 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.16 urn:nbn:de:0030-drops-138152 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.16 eng https://creativecommons.org/licenses/by/4.0/legalcode