Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework

Given a set $S$ of $n$ colored sites, each $s\in S$ associated with a distance-to-site function ${\delta }_s\text{\hspace{0.17em}⁣}:{\mathbb{R}}^2\to \mathbb{R}$, we consider two distance-to-color functions for each color: one takes the minimum of ${\delta }_s$ for sites $s\in 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 ${\delta }_s$ that satisfy certain conditions, including the case of point sites $S$ under convex distance functions and the $L_p$ metric for any $1\le p\le \mathrm{\infty }$. For the $L_1$ (or, $L_{\mathrm{\infty }}$) 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{)}^2\})$ complexity, while its maximal counterpart has $O(\min \{k(n-k),k^2\})$ 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 an iterative approach to compute higher-order color Voronoi diagrams.