2026-07-25T22:06:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23164 2025-10-02T12:41:39Z ddc:004 open_access

Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework Bae, Sang Won Oliver, Nicolau Papadopoulou, Evanthia higher-order Voronoi diagrams color Voronoi diagrams Hausdorff Voronoi diagrams colored j-facets arrangements Clarkson-Shor technique Given a set S of n colored sites, each s ∈ S associated with a distance-to-site function δ_s : ℝ² → ℝ, we consider two distance-to-color functions for each color: one takes the minimum of δ_s for sites s ∈ S in that color and the other takes the maximum. These two sets of distance functions induce two families of higher-order Voronoi diagrams for colors in the plane, namely, the minimal and maximal order-k color Voronoi diagrams, which include various well-studied Voronoi diagrams as special cases. In this paper, we derive an exact upper bound 4k(n-k)-2n on the total number of vertices in both the minimal and maximal order-k color diagrams for a wide class of distance functions δ_s that satisfy certain conditions, including the case of point sites S under convex distance functions and the L_p metric for any 1 ≤ p ≤ ∞. For the L_1 (or, L_∞) metric, and other convex polygonal metrics, we show that the order-k minimal diagram of point sites has O(min{k(n-k), (n-k)²}) complexity, while its maximal counterpart has O(min{k(n-k), k²}) complexity. To obtain these combinatorial results, we extend the Clarkson-Shor framework to colored objects, and demonstrate its application to several fundamental geometric structures, including higher-order color Voronoi diagrams, colored j-facets, and levels in the arrangements of piecewise linear/algebraic curves/surfaces. We also present iterative algorithms to compute higher-order color Voronoi diagrams. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sang Won Bae and Nicolau Oliver and Evanthia Papadopoulou 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.12 urn:nbn:de:0030-drops-231647 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.12 eng https://creativecommons.org/licenses/by/4.0/legalcode