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

Let $S$ be a set of $n$ sites, each of which is assigned a color from a set $K=\{1,\mathrm{\dots },m\}$ of $m$ colors. Let $S_i\subseteq S$ be the set of sites in color $i\in K$. We consider two distance-to-color functions from any point $x\in {ℝ}^2$ to each color $i\in K$:

where ${\delta }_s(x)$ denotes the prescribed distance-to-site function from $x\in {ℝ}^2$ to site $s\in S$.

Based on the two sets of point-to-color distances, we can define two different Voronoi diagrams of $m$ colors in $K$. For each $1⩽k⩽m-1$ and subset $H\subseteq K$ with $|H|=k$, define

called the minimal and maximal color Voronoi regions of $H$ with respect to $S$. We then define the order-$k$ minimal color Voronoi diagram of $S$, ${\mathrm{𝖢𝖵𝖣}}_k(S)$, to be the partition of ${ℝ}^2$ into the minimal regions $R_k(H;S)$, for all $H\subset K$ with $|H|=k$; the order-$k$ maximal color Voronoi diagram of $S$, ${\overline{\mathrm{𝖢𝖵𝖣}}}_k(S)$, to be the partition of ${ℝ}^2$ into the maximal regions ${\overline{R}}_k(H;S)$. In other words, ${\mathrm{𝖢𝖵𝖣}}_k(S)$ partitions ${ℝ}^2$ by $k$ nearest colors under the minimal distances ${\{d_i\}}_{i\in K}$, while ${\overline{\mathrm{𝖢𝖵𝖣}}}_k(S)$ partitions ${ℝ}^2$ by $k$ farthest colors under the maximal distances ${\{{\overline{d}}_i\}}_{i\in K}$.

These two families of color Voronoi diagrams generalize various conventional counterparts.

• $\mathrm{■}$

  For $k=1$, ${\mathrm{𝖢𝖵𝖣}}_1(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_1(S)$ correspond to the ordinary nearest-site and farthest-site Voronoi diagrams of $S$, $\mathrm{𝖵𝖣}(S)$ and $\mathrm{𝖥𝖵𝖣}(S)$, respectively, where adjacent faces of a common color are merged. See Figure 1(a) and (b).

• $\mathrm{■}$

  If $m=n$, that is, each site in $S$ has a distinct color, then ${\mathrm{𝖢𝖵𝖣}}_k(S)={\mathrm{𝖵𝖣}}_k(S)$, the ordinary order-$k$ Voronoi diagram without colors [29, 30, 13, 40]. In this case, it holds that ${\overline{\mathrm{𝖢𝖵𝖣}}}_k(S)={\mathrm{𝖵𝖣}}_{n-k}(S)$, also known as the order-$k$ farthest-site Voronoi diagram or the order-$k$ maximal Voronoi diagram [5].

• $\mathrm{■}$

  The farthest color Voronoi diagram $\mathrm{𝖥𝖢𝖵𝖣}(S)$ [24, 1, 32, 9] partitions the plane ${ℝ}^2$ into regions of colors $i\in K$ that consist of all points $p\in {ℝ}^2$ whose farthest color is $i$ with respect to the minimal distances ${\{d_i\}}_{i\in K}$. The Hausdorff Voronoi diagram $\mathrm{𝖧𝖵𝖣}(S)$, also known as the min-max or cluster Voronoi diagram [22, 37, 38], similarly partitions ${ℝ}^2$ into regions of nearest colors with respect to the maximal distances ${\{{\overline{d}}_i\}}_{i\in K}$. We thus have $\mathrm{𝖥𝖢𝖵𝖣}(S)={\mathrm{𝖢𝖵𝖣}}_{m-1}(S)$ and $\mathrm{𝖧𝖵𝖣}(S)={\overline{\mathrm{𝖢𝖵𝖣}}}_{m-1}(S)$. These two diagrams are often refined so that the region of each color $i\in K$ is subdivided into subregions of sites in $S_i$ that determine the distance-to-color $d_i$ or ${\overline{d}}_i$. We denote these refined versions by ${\mathrm{𝖥𝖢𝖵𝖣}}^{\ast }(S)$ and ${\mathrm{𝖧𝖵𝖣}}^{\ast }(S)$, respectively. See Figure 1(c) and (d).

In this paper, we initiate the study of higher-order color Voronoi diagrams, ${\mathrm{𝖢𝖵𝖣}}_k(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_k(S)$, with general distance functions ${\delta }_s$ for $s\in S$. Our main results are as follows:

1. (1)

   We prove an exact upper bound $4k(n-k)-2n$ on the total number of vertices of both order-$k$ diagrams ${\mathrm{𝖢𝖵𝖣}}_k(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_k(S)$ for each $1⩽k⩽m-1$, when the sites $s\in S$ are points and ${\delta }_s(x)$ is given as the convex distance from $x\in {ℝ}^2$ to $s$ based on any convex and compact subset of ${ℝ}^2$, which includes the $L_p$ distance for any $1⩽p⩽\mathrm{\infty }$. This result is in fact a corollary of our more general result: we derive an exact equation under certain conditions on functions ${\delta }_s$, which only requires relations on the numbers of vertices and unbounded edges in $\mathrm{𝖵𝖣}(S^{\prime })$ and $\mathrm{𝖥𝖵𝖣}(S^{\prime })$ for $S^{\prime }\subseteq S$. The bound $4k(n-k)-2n$ can be realized, for example, when $m=n$, so it is tight and best possible.

2. (2)

   Under the $L_1$ or the $L_{\mathrm{\infty }}$ metric, we prove that ${\mathrm{𝖢𝖵𝖣}}_k(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_k(S)$ consist of at most $\min \{4k(n-k)-2n,4{(n-k)}^2\}$ and $\min \{4k(n-k)-2n,2k^2\}$ vertices, respectively. Similar bounds are derived for any convex distance function based on a convex polygon.

3. (3)

   We present an iterative algorithm that computes color Voronoi diagrams of order $1$ to $k$ in $O(k^{2}n+n\log n)$ expected or $O(k^{2}n\log n)$ worst-case time, provided that $S$ and ${\{{\delta }_s\}}_{s\in S}$ satisfy the requirements of abstract Voronoi diagrams [28] and an additional condition (see Section 5), which includes colored points $S$ under any smooth convex distance function. For points $S$ in the Euclidean plane, it can be reduced to $O(k^{2}n+n\log n)$ worst-case time.

Our combinatorial results generalize previously known bounds for the ordinary higher-order Voronoi diagrams ${\mathrm{𝖵𝖣}}_k(S)$ of uncolored sites $S$, which is a special case of $m=n$ in our setting. The asymptotically tight bound $O(k(n-k))$ on the complexity of ${\mathrm{𝖵𝖣}}_k(S)$ has been proved not only for points [29, 30] under the $L_p$ metric but also for line segments [40] and even in the abstract setting [13]. Under the $L_1$ (or $L_{\mathrm{\infty }}$) metric, the complexity of ${\mathrm{𝖵𝖣}}_k(S)$ is known to be $O(\min \{k(n-k),{(n-k)}^2\})$ for a set $S$ of points or line segments [30, 40].

In particular, the same exact number $4k(n-k)-2n$ can be derived for the ordinary order-$k$ diagram ${\mathrm{𝖵𝖣}}_k(S)$ and order-$(n-k)$ diagram ${\mathrm{𝖵𝖣}}_{n-k}(S)$ under the Euclidean metric from previous results [21, 29, 20]. In his book [21, Chapter 13], Edelsbrunner showed that the number of vertices of ${\mathrm{𝖵𝖣}}_k(S)$ is exactly $(4k-2)n-2k^2-e_k-2{\sum }_{i=1}^{k-1}{e}_i$, if $S$ is in general position, where $e_k$ denotes the number of unbounded edges in ${\mathrm{𝖵𝖣}}_k(S)$ (or, equivalently, $k$-sets in $S$). One can easily verify that the total number of vertices in ${\mathrm{𝖵𝖣}}_k(S)$ and ${\mathrm{𝖵𝖣}}_{n-k}(S)$ is exactly $4k(n-k)-2n$ by using the identities: $e_k=e_{n-k}$ and ${\sum }_{k=1}^{n-1}{e}_k=n(n-1)$. This can also be verified from the inductive approach of Lee [29]. As a recent result related to ours, Biswas et al. [12] derived exact relations for the complexity of 3D Euclidean higher-order Voronoi diagrams with Morse theory, extending the inductive argument by Lee.

Another remarkable special case of our results is when $k=m-1$, which yields the $O(m(n-m+1))$ bound for the farthest color Voronoi diagram $\mathrm{𝖥𝖢𝖵𝖣}(S)={\mathrm{𝖢𝖵𝖣}}_{m-1}(S)$ and the Hausdorff Voronoi diagram $\mathrm{𝖧𝖵𝖣}(S)={\overline{\mathrm{𝖢𝖵𝖣}}}_{m-1}(S)$. The worst-case complexity of $\mathrm{𝖥𝖢𝖵𝖣}(S)$ and $\mathrm{𝖧𝖵𝖣}(S)$ is known to be $\mathrm{\Theta }(mn)$ or $\mathrm{\Theta }(n^2)$, if $S$ is a set of points or line segments under the Euclidean or $L_1$ metric [22, 24, 1, 38, 9]. While the upper bounds $O(mn)$ and $O(n^2)$ are shown to be tight by matching lower bound constructions [24, 1, 22], they become significantly loose when $n$ is close to $m$; if $n=m$, we have $\mathrm{𝖥𝖢𝖵𝖣}(S)=\mathrm{𝖥𝖵𝖣}(S)$ and $\mathrm{𝖧𝖵𝖣}(S)=\mathrm{𝖵𝖣}(S)$, where both have linear complexity. Hence, our new results not only prove tight upper bounds simultaneously on both diagrams, but also formally reveal a smooth extension upon the previous knowledge about the ordinary Voronoi diagrams for any $m⩽n$. Prior to our results, it was known that the complexity of $\mathrm{𝖥𝖢𝖵𝖣}(S)$ and $\mathrm{𝖧𝖵𝖣}(S)$ can range from $\mathrm{\Theta }(n)$ to $\mathrm{\Theta }(m(n-m+1))$ expressed in terms of geometric parameters, called straddles for $\mathrm{𝖥𝖢𝖵𝖣}(S)$ [33] and crossings for $\mathrm{𝖧𝖵𝖣}(S)$ [38]. Conditions under which these diagrams have linear complexity have also been discussed [38, 33, 8].

Our combinatorial results are based on a color-augmented extension of the Clarkson–Shor framework [20], so-called the colorful Clarkson–Shor framework, which has its own interest with various applications. Our notions of colored objects and configurations are naturally inherited from any set system that fits in the original Clarkson–Shor framework, and yield a systematic scheme to deal with objects that are collections of primitive elements. Our new framework provides a unifying approach to derive the complexity of higher-order color Voronoi diagrams under general distances ${\delta }_s$, including the well-studied diagrams $\mathrm{𝖥𝖢𝖵𝖣}(S)$, $\mathrm{𝖧𝖵𝖣}(S)$, and the ordinary higher-order diagram ${\mathrm{𝖵𝖣}}_k(S)$. In deriving our results, we make use of a close relation between the color diagrams ${\mathrm{𝖢𝖵𝖣}}_k(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_k(S)$ and the colored $k$-facets of $S$. An analogous relation for the Euclidean ordinary case (without colors) has been shown by Clarkson and Shor [20] and Edelsbrunner [21]. We also derive lower and upper bounds on the number of colored $k$-facets in ${ℝ}^2$. We also demonstrate more applications of the colorful Clarkson–Shor framework that result in several new bounds on levels of arrangements of piecewise linear or algebraic curves and surfaces; see [10].

Our algorithm follows the principle of iteratively computing all order-$i$ Voronoi diagrams for $1⩽i⩽k$, and compares to the $O(k^{2}n\log n)$-time counterpart of Lee [29] for computing ${\mathrm{𝖵𝖣}}_1(S),\mathrm{\dots },{\mathrm{𝖵𝖣}}_k(S)$ for points in the Euclidean metric. After a series of improvements [3, 7, 36, 2, 16, 41, 18], the first optimal $O(n\log n+kn)$-time algorithm that computes ${\mathrm{𝖵𝖣}}_k(S)$ for points $S$ in the Euclidean plane was eventually presented in 2024 by Chan et al. [17]. Efficient algorithms of different approaches are also known for computing ${\mathrm{𝖵𝖣}}_k(S)$ of line segments $S$ [40] or under the model of abstract Voronoi diagrams [14, 15]; and for computing ${\mathrm{𝖥𝖢𝖵𝖣}}^{\ast }(S)$ [24, 1, 9, 33] and ${\mathrm{𝖧𝖵𝖣}}^{\ast }(S)$ [22, 38, 4].

Due to space limit, proofs are omitted but can be found in the full version [10].

Let $S$ be a set of $n$ sites, which can be any abstract objects, and ${\delta }_s:{ℝ}^2\to ℝ$ for $s\in S$ be a given continuous function. We assume that the functions ${\delta }_s$ are in general position, similarly to [26]. More precisely, let ${\gamma }_s$ be the graph of ${\delta }_s$, that is, the $xy$-monotone surface $\{(p,{\delta }_s(p))\mid p\in {ℝ}^2\}$ in ${ℝ}^3$, and $\mathrm{\Gamma }:=\{{\gamma }_s\mid s\in S\}$. By the general position of functions ${\delta }_s$, we mean the following: no more than three surfaces in $\mathrm{\Gamma }$ meet at a common point, no more than two surfaces in $\mathrm{\Gamma }$ meet at a one-dimensional curve, no two surfaces in $\mathrm{\Gamma }$ are tangent to each other, and none of the surfaces in $\mathrm{\Gamma }$ is tangent to the intersection curve of two others in $\mathrm{\Gamma }$.

We denote the minimization diagram of $\mathrm{\Gamma }$ by $\mathrm{𝖵𝖣}(S)$, the nearest-site Voronoi diagram of $S$, and the maximization diagram of $\mathrm{\Gamma }$ by $\mathrm{𝖥𝖵𝖣}(S)$, the farthest-site Voronoi diagram of $S$. It is well known that the ordinary (uncolored) higher-order Voronoi diagrams ${\mathrm{𝖵𝖣}}_k(S)$ of $S$ are determined by levels of the arrangement $𝒜(\mathrm{\Gamma })$ of $\mathrm{\Gamma }$ as established in earlier work [23, 5]. In the following, we discuss an analogous relation between order-$k$ color Voronoi diagrams and levels of certain surfaces in ${ℝ}^3$.

Let us assume that the sites in $S$ are colored with $m$ colors in $K=\{1,\mathrm{\dots },m\}$. Let $\kappa :S\to K$ denote a color assignment such that the color of $s\in S$ is $\kappa (s)\in K$. Let $S_i:=\{s\in S\mid \kappa (s)=i\}$ and ${\mathrm{\Gamma }}_i:=\{{\gamma }_s\mid s\in S_i\}$ for $i\in K$. Define $E_i$ and ${\overline{E}}_i$ to be the lower and upper envelopes of surfaces in ${\mathrm{\Gamma }}_i$, respectively, and consider the two arrangements ${𝒜}_{\mathrm{\Gamma }}=𝒜(\{E_1,\mathrm{\dots },E_m\})$ and ${\overline{𝒜}}_{\mathrm{\Gamma }}=𝒜(\{{\overline{E}}_1,\mathrm{\dots },{\overline{E}}_m\})$. Note that $E_i$ is the graph of the minimal distance function $d_i$ of color $i\in K$, and ${\overline{E}}_i$ is the graph of the maximal distance ${\overline{d}}_i$. We then consider the levels of the arrangements ${𝒜}_{\mathrm{\Gamma }}$ and ${\overline{𝒜}}_{\mathrm{\Gamma }}$. For $1⩽k⩽m$, let $L_k$ be the $k$-level of ${𝒜}_{\mathrm{\Gamma }}$ from below and ${\overline{L}}_k$ be the $k$-level of ${\overline{𝒜}}_{\mathrm{\Gamma }}$ from above. So, $L_1$ is the lower envelope of $E_1,\mathrm{\dots },E_m$, and ${\overline{L}}_1$ is the upper envelope of ${\overline{E}}_1,\mathrm{\dots },{\overline{E}}_m$. Thus, projecting $L_1$ and ${\overline{L}}_1$ down onto ${ℝ}^2$ yields $\mathrm{𝖵𝖣}(S)$ and $\mathrm{𝖥𝖵𝖣}(S)$, respectively. On the other hand, $L_m$ is the upper envelope of the lower envelopes $E_1,\mathrm{\dots },E_m$, and ${\overline{L}}_m$ is the lower envelope of the upper envelopes ${\overline{E}}_1,\mathrm{\dots },{\overline{E}}_m$. Projecting $L_m$ and ${\overline{L}}_m$ down onto ${ℝ}^2$ yields the refined diagrams ${\mathrm{𝖥𝖢𝖵𝖣}}^{\ast }(S)$ and ${\mathrm{𝖧𝖵𝖣}}^{\ast }(S)$, respectively [24, 22].

From the viewpoint of [23, 5], we observe the following.

• $\mathrm{■}$

  The order-$k$ color Voronoi diagrams, ${\mathrm{𝖢𝖵𝖣}}_k(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_k(S)$, for $1⩽k⩽m-1$ are the projections of $L_k\cap L_{k+1}$ and of ${\overline{L}}_k\cap {\overline{L}}_{k+1}$, respectively, onto ${ℝ}^2$.

• $\mathrm{■}$

  For each $1⩽k⩽m$, let ${\mathrm{𝖢𝖵𝖣}}_k^{\ast }(S)$ denote the planar map obtained by projecting $L_k$ down onto ${ℝ}^2$; analogously, let ${\overline{\mathrm{𝖢𝖵𝖣}}}_k^{\ast }(S)$ be the map obtained by projecting ${\overline{L}}_k$ onto ${ℝ}^2$. By definition, ${\mathrm{𝖢𝖵𝖣}}_k^{\ast }(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_k^{\ast }(S)$ refine ${\mathrm{𝖢𝖵𝖣}}_k(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_k(S)$, respectively. Each face $f$ of ${\mathrm{𝖢𝖵𝖣}}_k^{\ast }(S)$ (or of ${\overline{\mathrm{𝖢𝖵𝖣}}}_k^{\ast }(S)$) is associated with a site $s\in S_i$ such that, for any point $p\in f$, $d_i(p)={\delta }_s(p)$ and $i\in K$ is the $k$-th nearest color from $p$ with respect to ${\{d_i\}}_{i\in K}$ (resp. ${\overline{d}}_i(p)={\delta }_s(p)$ and $i\in K$ is the $k$-th farthest color from $p$ with respect to ${\{{\overline{d}}_i\}}_{i\in K}$). This way, the refined diagrams ${\mathrm{𝖢𝖵𝖣}}_k^{\ast }(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_k^{\ast }(S)$ partition the plane ${ℝ}^2$ by the $k$-th nearest and $k$-th farthest colors, respectively.

From the construction, it is clear that ${\mathrm{𝖢𝖵𝖣}}_1^{\ast }(S)=\mathrm{𝖵𝖣}(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_1^{\ast }(S)=\mathrm{𝖥𝖵𝖣}(S)$. Note also that ${\mathrm{𝖢𝖵𝖣}}_m^{\ast }(S)={\mathrm{𝖥𝖢𝖵𝖣}}^{\ast }(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_m^{\ast }(S)={\mathrm{𝖧𝖵𝖣}}^{\ast }(S)$, whereas $\mathrm{𝖥𝖢𝖵𝖣}(S)={\mathrm{𝖢𝖵𝖣}}_{m-1}(S)$ and $\mathrm{𝖧𝖵𝖣}(S)={\overline{\mathrm{𝖢𝖵𝖣}}}_{m-1}(S)$.

Figures 2 and 3 illustrate an example under the Euclidean metric, where $S$ consists of $n=9$ points and $m=4$ colors: $S_1=\{s_1,s_2,s_5\}$, $S_2=\{s_3,s_9\}$, $S_3=\{s_4,s_6,s_8\}$, and $S_4=\{s_7\}$, in red, blue, purple, and black, respectively; selected regions of ${\mathrm{𝖢𝖵𝖣}}_k(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_k(S)$ are labeled in (a)–(c); faces associated with $s_6\in S_3$ and those with $s_9\in S_2$ in ${\mathrm{𝖢𝖵𝖣}}_k^{\ast }(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_k^{\ast }(S)$ are shaded in purple and blue, respectively, in (d)–(g).

Now, consider the vertices and edges of the arrangements ${𝒜}_{\mathrm{\Gamma }}$ and ${\overline{𝒜}}_{\mathrm{\Gamma }}$. By the general position assumption, each vertex $v$ of ${𝒜}_{\mathrm{\Gamma }}$ or of ${\overline{𝒜}}_{\mathrm{\Gamma }}$ is determined by exactly three sites $s,s^{\prime },s^{\prime \prime }\in S$ in such a way that $v$ is a common intersection of three surfaces ${\gamma }_s,{\gamma }_{s^{\prime }},{\gamma }_{s^{\prime \prime }}\in \mathrm{\Gamma }$. Such a vertex $v$ is called $c$-chromatic for $c\in \{1,2,3\}$ if $|\{\kappa (s),\kappa (s^{\prime }),\kappa (s^{\prime \prime })\}|=c$. (Note that any $1$-chromatic vertex is a vertex of some single envelope $E_i$ or ${\overline{E}}_i$.) Similarly, each edge of ${𝒜}_{\mathrm{\Gamma }}$ and of ${\overline{𝒜}}_{\mathrm{\Gamma }}$ is determined by exactly two sites in $S$, and is either $1$- or $2$-chromatic according to the number of involved colors. We identify each vertex or edge of ${\mathrm{𝖢𝖵𝖣}}_k^{\ast }(S)$ or of ${\overline{\mathrm{𝖢𝖵𝖣}}}_k^{\ast }(S)$ by its original lifted copy in ${𝒜}_{\mathrm{\Gamma }}$ or in ${\overline{𝒜}}_{\mathrm{\Gamma }}$. Observe that any $c$-chromatic vertex or edge of ${𝒜}_{\mathrm{\Gamma }}$ or of ${\overline{𝒜}}_{\mathrm{\Gamma }}$ appears in $c$ consecutive levels, as it lies in the intersection of $c$ surfaces from ${\{E_i\}}_{i\in K}$ or from ${\{{\overline{E}}_i\}}_{i\in K}$, respectively. Thus, $c$-chromatic vertices appear in $c$ consecutive orders of the refined diagrams. We call a vertex or an edge of ${\mathrm{𝖢𝖵𝖣}}_k^{\ast }(S)$ or of ${\overline{\mathrm{𝖢𝖵𝖣}}}_k^{\ast }(S)$ new if it does not appear in ${\mathrm{𝖢𝖵𝖣}}_{k-1}^{\ast }(S)$ or in ${\overline{\mathrm{𝖢𝖵𝖣}}}_{k-1}^{\ast }(S)$, respectively; and old, otherwise. By definition, the vertices and edges of ${\mathrm{𝖢𝖵𝖣}}_1^{\ast }(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_1^{\ast }(S)$ are all new. Note that every edge of ${\mathrm{𝖢𝖵𝖣}}_k(S)$ (or, of ${\overline{\mathrm{𝖢𝖵𝖣}}}_k(S)$) is $2$-chromatic and new, and appears both in ${\mathrm{𝖢𝖵𝖣}}_k^{\ast }(S)$ and ${\mathrm{𝖢𝖵𝖣}}_{k+1}^{\ast }(S)$ (in ${\overline{\mathrm{𝖢𝖵𝖣}}}_k^{\ast }(S)$ and ${\overline{\mathrm{𝖢𝖵𝖣}}}_{k+1}^{\ast }(S)$, resp.), being first new and then old. See Figures 2 and 3, where new $2$-chromatic edges are in black, old $2$-chromatic edges in gray, $1$-chromatic edges in their own color, and new vertices marked by small squares.

We define $v_{c,j}=v_{c,j}(S)$ for $1⩽c⩽3$ and $0⩽j⩽m-1$ to be the number of $c$-chromatic vertices in ${𝒜}_{\mathrm{\Gamma }}$ below which there are exactly $j$ surfaces from ${\{E_i\}}_{i\in K}$; ${\overline{v}}_{c,j}={\overline{v}}_{c,j}(S)$ to be the number of $c$-chromatic vertices in ${\overline{𝒜}}_{\mathrm{\Gamma }}$ above which there are exactly $j$ surfaces from ${\{{\overline{E}}_i\}}_{i\in K}$.

The Clarkson–Shor technique [20] is based on a general framework dealing with so-called configurations or ranges defined by a set of objects. Specifically, the following three ingredients are supposed to be given with a constant integer parameter $d⩾1$, see also Sharir [42]:

• $\mathrm{■}$

  A set $S$ of $n$ objects.

• $\mathrm{■}$

  A set $ℱ(S)$ of configurations, each of which is defined by exactly $d$ objects in $S$.

• $\mathrm{■}$

  A conflict relation $\chi \subseteq S\times ℱ(S)$ between objects $s\in S$ and configurations $f\in ℱ(S)$ with the requirement that none of the $d$ objects defining $f$ are in conflict with $f$.

In the original framework, the number of objects that define a configuration does not have to be exactly $d$, but at most $d$. This restriction can be achieved by adding dummy objects to $S$.

Let us call such a triplet $(S,ℱ(S),\chi )$ a CS-structure. Given any CS-structure $(S,ℱ(S),\chi )$ with parameter $d$, we now impose a color assignment $\kappa :S\to K$ to the objects in $S$, where $K=\{1,2,\mathrm{\dots },m\}$ denotes the set of $m$ colors with $m⩽n$. For each color $i\in K$, let $S_i:=\{s\in S\mid \kappa (s)=i\}$. For $f\in ℱ(S)$ and set $D_f\subseteq S$ of $d$ objects defining $f$, $\kappa (D_f)=\{\kappa (s)\mid s\in D_f\}$ is called a set of colors defining $f$. We build a color-to-configuration conflict relation ${\chi }_{\kappa }\subseteq K\times ℱ(S)$ such that a color $i\in K$ is in conflict with a configuration $f\in ℱ(S)$ if an object $s\in S_i$ is in conflict with $f$, that is, $(i,f)\in {\chi }_{\kappa }$ if and only if $(s,f)\in \chi$ for some $s\in S_i$. We are then interested in those configurations $f\in ℱ(S)$ such that none of its defining colors in $\kappa (D_f)$ are in conflict with $f$. Let $ℱ(S,\kappa )\subseteq ℱ(S)$ be the set of these configurations, called colored configurations with respect to $\kappa$. We call $f\in ℱ(S,\kappa )$ $c$-chromatic if $|\kappa (D_f)|=c$ for $1⩽c⩽d$, and let the weight of $f$ be the number of colors in $K$ that are in conflict with $f$. Let ${ℱ}_{c,j}(S,\kappa )\subseteq ℱ(S,\kappa )$ be the set of $c$-chromatic weight-$j$ colored configurations in $ℱ(S,\kappa )$.

Considering the colors in $K$ as new objects, each of which is a collection of objects in $S$, observe that this color-augmented structure $(K,{\bigcup }_j{ℱ}_{c,j}(S,\kappa ),{\chi }_{\kappa })$ for each $1⩽c⩽d$ is again a CS-structure with parameter $c$. Therefore, the main lemma of Clarkson and Shor [20, Lemma 2.1] automatically implies the following.

In probabilistic arguments dealing with CS-structures, it is usually necessary to have an upper bound on the number of weight-$0$ configurations. For any subset $S^{\prime }\subseteq S$, let ${ℱ}_0(S^{\prime })\subseteq ℱ(S^{\prime })$ be the set of (uncolored) configurations $f$ of weight 0, that is, $(s,f)\notin \chi$ for all $s\in S^{\prime }$. Let $T_0(n^{\prime })$ be any nondecreasing function with $T_0(0)=0$ that upper bounds the number $|{ℱ}_0(S^{\prime })|$ of these configurations for any set $S^{\prime }$ of $n^{\prime }$ uncolored objects. The following is obvious by definition.

In many applications, such an upper bound function $T_0$ is either known from previous work or relatively easy to obtain. Once we have $T_0$, we can derive general upper bounds on the number of corresponding colored configurations of weight at most $k$ in such a procedural way as done for uncolored cases [43, 20, 34].

Remark that the left-hand side of the first bound can be seen as a “weighted” count of $(⩽c)$-chromatic colored configurations, and that the second bound in Theorem 4 for $n=m$ implies Clarkson and Shor’s original bound, $O({(k+1)}^c\cdot T_0(n/(k+1)))$, for uncolored cases [20, Theorem 3.1]. Note that Theorem 4 still implies the same Clarkson–Shor bound if $T_0$ is linear. Moreover, if the colors are assigned in a favorably uniform way, we can derive similar bounds as well without assuming the convexity of $T_0$.

We extend our results for the Euclidean case to general distance functions. We continue the discussions from Section 2, so $S$ is a set of $n$ sites, colored with $m$ colors from $K$ by a color assignment $\kappa$, and the functions ${\delta }_s:{ℝ}^2\to ℝ$ for $s\in S$ are in general position.

Notice that the vertices of the arrangements ${𝒜}_{\mathrm{\Gamma }}$ and ${\overline{𝒜}}_{\mathrm{\Gamma }}$ form two set systems that fit in our colorful framework. More precisely, let $ℱ(S)$ be the set of vertices of the arrangement of $n$ surfaces in $\mathrm{\Gamma }$, and consider two conflict relations $\chi ,\overline{\chi }\subseteq S\times ℱ(S)$ such that $(s,v)\in \chi$ if $v\in ℱ(S)$ lies above surface ${\gamma }_s\in \mathrm{\Gamma }$ and $(s,v)\in \overline{\chi }$ if $v$ lies below ${\gamma }_s$. Based on two CS-structures $(S,ℱ(S),\chi )$ and $(S,ℱ(S),\overline{\chi })$, we consider their colored configurations with respect to $\kappa$, denoted by $ℱ(S,\kappa )$ and $\overline{ℱ}(S,\kappa )$, respectively. By this construction, we have $v_{c,j}(S)=|{ℱ}_{c,j}(S,\kappa )|$ and ${\overline{v}}_{c,j}(S)=|{\overline{ℱ}}_{c,j}(S,\kappa )|$, counting $c$-chromatic weight-$j$ colored configurations in $ℱ(S,\kappa )$ and in $\overline{ℱ}(S,\kappa )$, respectively, and, simultaneously, counting new $c$-chromatic vertices in ${\mathrm{𝖢𝖵𝖣}}_{j+1}^{\ast }(S)$ and in ${\overline{\mathrm{𝖢𝖵𝖣}}}_{j+1}^{\ast }(S)$ by Lemma 1.

For each $S^{\prime }\subseteq S$, let $v_0(S^{\prime })$ and $u_0(S^{\prime })$ denote the numbers of vertices and unbounded edges¹¹1Hereafter, by counting unbounded edges, we mean counting vertices at infinity. So, if an unbounded edge separates the plane ${ℝ}^2$, then it is counted twice. , respectively, in $\mathrm{𝖵𝖣}(S^{\prime })$; let ${\overline{v}}_0(S^{\prime })$ and ${\overline{u}}_0(S^{\prime })$ denote the numbers of vertices and unbounded edges, respectively, in $\mathrm{𝖥𝖵𝖣}(S^{\prime })$. We consider the following conditions.

V1

$v_0(S^{\prime })=2|S^{\prime }|-2-u_0(S^{\prime })$ for any $S^{\prime }\subseteq S$.

V2

${\overline{v}}_0(S^{\prime })={\overline{u}}_0(S^{\prime })-2$ for any $S^{\prime }\subseteq S$.

Note that if every region in $\mathrm{𝖵𝖣}(S^{\prime })$ is nonempty and simply connected, then Euler’s formula and the general position assumption imply condition V1. If $\mathrm{𝖥𝖵𝖣}(S^{\prime })$ forms a tree, then every face of $\mathrm{𝖥𝖵𝖣}(S^{\prime })$ is unbounded and thus condition V2 holds by Euler’s formula.

In addition, for $c\in \{1,2\}$ and $j⩾0$, let $u_{c,j}=u_{c,j}(S)$ be the number of $c$-chromatic unbounded edges in ${𝒜}_{\mathrm{\Gamma }}$ that lie above exactly $j$ surfaces in ${\{E_i\}}_{i\in K}$, and ${\overline{u}}_{c,j}={\overline{u}}_{c,j}(S)$ be the number of $c$-chromatic unbounded edges in ${\overline{𝒜}}_{\mathrm{\Gamma }}$ that lie below exactly $j$ surfaces in ${\{{\overline{E}}_i\}}_{i\in K}$. From the discussion in Section 2, observe that $u_{c,j}$ and ${\overline{u}}_{c,j}$ are equal to the numbers of new $c$-chromatic unbounded edges in ${\mathrm{𝖢𝖵𝖣}}_{j+1}^{\ast }(S)$ and in ${\overline{\mathrm{𝖢𝖵𝖣}}}_{j+1}^{\ast }(S)$, respectively. Further, as for $v_{c,j}$ and ${\overline{v}}_{c,j}$, note that $u_{c,j}$ and ${\overline{u}}_{c,j}$ indeed count $c$-chromatic weight-$j$ colored configurations based on two CS-structures for unbounded edges in the arrangement of $n$ surfaces in $\mathrm{\Gamma }$. Hence, assuming V1 and V2, Lemma 3 implies: for any subset $R\subseteq K$,