Abstract Color Voronoi Diagrams and Circular Sequences of Color Permutations
2026-07-06 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study a mathematical structure called higher-order abstract color Voronoi diagrams, which group points based on distances to colored sites in a plane. They provide a formula to limit how complex these diagrams can get, measured by the number of vertices, and offer a method to build them step-by-step. Their results apply broadly, including to shapes like simple polygons, and include an interesting part of their proof using patterns in color arrangements on the diagram edges.
Voronoi diagramabstract Voronoi diagramhigher-order Voronoi diagramcolor Voronoi diagramplanar bisecting curvescombinatorial propertiessimple polygonscircular sequencescolor permutationscomputational geometry
Authors
Sang Won Bae, Nicolau Oliver, Evanthia Papadopoulou
Abstract
Abstract Voronoi diagrams are defined in terms of a given system of planar bisecting curves satisfying some simple combinatorial properties. They offer a unifying framework for a wide range of concrete Voronoi instances on generalized sites and metrics. In this paper, we formulate higher-order abstract color Voronoi diagrams of a set $S$ of $n$ colored abstract sites, simultaneously considering all concrete instances under their umbrella. We prove that the number of vertices in the order-$k$ abstract color Voronoi diagram is at most $4k(n-k)-2n$, and present an iterative construction algorithm. The bound directly applies to a family of $m$ disjoint simple polygons of total complexity $n$. For simple polygons the bound can further improve to $O(\min\{k(n-k),(m-k)^2n\})$. A critical ingredient of our proof is a combinatorial analysis on circular sequences of color permutations derived from the unbounded edges of these diagrams, which is interesting in its own right.