Proof. It is enough to show that for colors \(a,b,c \in K\) \[\mathop{\mathrm{cl}}D({a},{b}) \cap \mathop{\mathrm{cl}}D({b},{c}) \subseteq \mathop{\mathrm{cl}}D({a},{c}) \quad\text{and}\quad \mathop{\mathrm{cl}}\overline{D}({a},{b}) \cap \mathop{\mathrm{cl}}\overline{D}({b},{c}) \subseteq \mathop{\mathrm{cl}}\overline{D}({a},{c}).\] Let \(x \in \mathop{\mathrm{cl}}D({a},{b}) \cap \mathop{\mathrm{cl}}D({b},{c})\). Then \(x\in \mathop{\mathrm{cl}}\mathrm{VR}(p_a, S_a\cup S_b)\) and \(x\in \mathop{\mathrm{cl}}\mathrm{VR}(p_b, S_b\cup S_c)\), for some site \(p_a \in S_a\) and \(p_b \in S_b\). It follows that \(x\in \mathop{\mathrm{cl}}\mathrm{VR}(p_a, S_a\cup S_b\cup S_c)\) by the standard transitivity property of ordinary Voronoi regions. Then \(x\in \mathop{\mathrm{cl}}\mathrm{VR}(p_a, S_a\cup S_c)\), and consequently, \(x\in \mathop{\mathrm{cl}}D({a},{c})\). The transitivity of \(\mathrel{\overline{\succcurlyeq}}_x\) based on the maximal dominance can be proved analogously using the diagrams \(\mathsf{FVD}(S_a\cup S_b)\) and \(\mathsf{FVD}(S_b\cup S_c)\). ◻

Proof. As already stated, Lemma [lem:transitivity] implies that \(\preccurlyeq_x\) and \(\mathrel{\overline{\succcurlyeq}}_x\) induce two orderings of the \(m\) colors in \(K\) at any point \(x\in\mathbb{R}^2\): \(a_1 \preccurlyeq_x \cdots \preccurlyeq_x a_m\) and \(\bar{a}_1 \mathrel{\overline{\succcurlyeq}}_x \cdots \mathrel{\overline{\succcurlyeq}}_x \bar{a}_m\). Then \(x\in\mathop{\mathrm{cl}}\mathrm{R}_k(H_x, S)\), where \(H_x=\{a_1, \ldots, a_k\}\), and \(x\in\mathop{\mathrm{cl}}\overline{\mathrm{R}}_k(\bar{H}_x, S)\), where \(\bar{H}_x=\{\bar{a}_1, \ldots, \bar{a}_k\}\). Since every point \(x \in \mathbb{R}^2\) is contained in at least one such region, the union of their closures covers the plane. ◻

Proof. It follows from Lemma [lem:transitivity] that each point \(x\) in \(\mathrm{R}_k(H, S)\) (resp., \(\overline{\mathrm{R}}_k(H,S)\)) has a unique set of \(k\) nearest (resp., farthest) colors. Thus, two distinct regions \(\mathrm{R}_k(H, S)\) and \(\mathrm{R}_k(H', S)\) (resp., \(\overline{\mathrm{R}}_k(H,S)\) and \(\overline{\mathrm{R}}_k(H', S)\)) must have empty intersection. Since these regions cover the plane by Lemma [lem:cvrk95covers95plane], their boundary, and thus \(\mathsf{CVD}_{k}\) (resp., \(\overline{\mathsf{CVD}}_{k}\)) is exactly the union of intersections of their closures. ◻

Proof. Let \(p\in E\) and let \(a_1 \preccurlyeq_p \cdots \preccurlyeq_p a_k\preccurlyeq_p a_{k+1}\) be the ordering of the first \(k+1\) colors with respect to the minimal dominance relation \(\preccurlyeq_p\). Since \(p\) is on the boundary of both \(\mathrm{R}_k(H, S)\) and \(\mathrm{R}_k(H', S)\), it follows that \(a_k \sim_p a_{k+1}\), and \(p\in J({a_k},{a_{k+1}})\).

Let \(x \in \mathrm{R}_k(H, S)\cap N(p)\) and \(x' \in \mathrm{R}_k(H', S)\cap N(p)\) be points in a very small neighborhood \(N(p)\) around \(p\). By continuity, colors \(a_1 ...a_{k-1}\) are the first \(k-1\) colors with respect to both the minimal dominance relations \(\preccurlyeq_x\) and \(\preccurlyeq_{x'}\), while the \(k\)-th color is \(a_k\) for one and \(a_{k+1}\) for the other. The claim follows, where \(a=a_k\) and \(a'=a_{k+1}\) if \(D({a},{a'})\) lies in the same side of \(J({a},{a'})\) as \(x\). ◻

Proof. Let \(x\) be a Voronoi vertex of \(\mathsf{CVD}_k(S)\), where \(x \in \mathop{\mathrm{cl}}\mathrm{R}_k(H_1, S) \cap \mathop{\mathrm{cl}}\mathrm{R}_k(H_2,S) \cap \mathop{\mathrm{cl}}\mathrm{R}_k(H_3,S)\). By Lemma [lem:neighboring-regions] we have \(|H_i \cap H_j| = k-1\) and \(|H_i \setminus H_j| = 1\) for any pair of distinct indices \(i,j \in \{1,2,3\}\). This implies only two possibilities: either \(|H_1 \cap H_2 \cap H_3| = k-1\) or \(|H_1 \cap H_2 \cap H_3| = k-2\). In the former case, we have \(H_1 \cap H_2 \cap H_3 = \{a_1, \ldots, a_{k-1}\}\), \(H_1 \cup H_2 \cup H_3 = \{a_1, \ldots, a_{k+2}\}\), and \(a_{k-1} \prec_x a_{k} \sim_x a_{k+1} \sim_x a_{k+2} \prec_x a_{k+3}\), thus, \(x\) must be new in \(\mathsf{CVD}_k(S)\) as \(x\not\in \mathsf{CVD}_{k-1}(S)\). In the latter case, we have \(H_1 \cap H_2 \cap H_3 = \{a_1, \ldots, a_{k-2}\}\), \(H_1 \cup H_2 \cup H_3 = \{a_1, \ldots, a_{k+1}\}\), and \(a_{k-2} \prec_x a_{k-1} \sim_x a_{k} \sim_x a_{k+1} \prec_x a_{k+2}\). Then, \(x\) is a vertex of \(\mathsf{CVD}_{k-1}(S)\), and consequently old in \(\mathsf{CVD}_k(S)\). It is now obvious that an old vertex of \(\mathsf{CVD}_k(S)\) is a new vertex of \(\mathsf{CVD}_{k-1}(S)\), and is not a vertex of \(\mathsf{CVD}_{j}(S)\) for any \(j \notin \{k,k-1\}\). Similarly, no Voronoi edge of \(\mathsf{CVD}_{k}(S)\) can remain in \(\mathsf{CVD}_{k+1}(S)\). ◻

Proof. Since \(R\subseteq \mathrm{R}_k(H, S)\) and \(|H|=k\), it follows that \(\mathsf{CVD}_{k-1}(S) \cap R = \mathsf{CVD}_{k-1}(S_H) \cap R\). But \(\mathsf{CVD}_{k-1}(S_H)= \mathsf{FCVD}(S_H)\), thus, the first claim follows. Analogously, for \(\overline{R} \subseteq \overline{\mathrm{R}}_k(H, S)\), as \(\mathsf{HVD}(S_H) = \overline{\mathsf{CVD}}_{k-1}(S_H)\), while \(\overline{\mathsf{CVD}}_{k-1}(S)\cap \overline{R}=\overline{\mathsf{CVD}}_{k-1}(S_H)\cap \overline{R}\).

The superimposition property follows since \(\mathsf{CVD}^*_k(S) \cap R=\mathsf{FCVD}^*(S_H)\cap R\), and \(\mathsf{FCVD}(S_H)\cap R= \mathsf{CVD}_{k-1}(S_H)\) as already shown. ◻

Proof. Consider a \(3\)-chromatic new vertex \(v\) of \(\mathsf{CVD}_k(S)\). By Lemma [lem:vertex95characterization], \(v\) is an old vertex in \(\mathsf{CVD}_{k+1}(S)\), and it does not appear in \(\mathsf{CVD}_{k+2}(S)\). In fact, it cannot appear in \(\mathsf{CVD}_{j}(S)\) for any \(j\notin \{k,k+1\}\) (see proof of Lemma [lem:vertex95characterization]). However, by Lemma [lem:overlay95CVDk95star], \(v\) appears in \(\mathsf{CVD}_{k+2}^*(S)\). Thus, the claim follows for \(c=3\).

Next, consider a \(2\)-chromatic edge \(e\) in \(\mathsf{CVD}_k(S)\) (and any \(2\)-chromatic vertex \(v\) that \(e\) may contain). By Lemma [lem:vertex95characterization], the edge \(e\) does not appear in \(\mathsf{CVD}_{k+1}(S)\), nor can it appear in any \(\mathsf{CVD}_{j}(S)\) for \(j\neq k\); however, it appears in \(\mathsf{CVD}^*_{k+1}(S)\), by Lemma [lem:overlay95CVDk95star]. Thus, the claim follows for \(c=2\).

Finally, consider a \(1\)-chromatic edge \(e\) (resp. vertex) defined by sites of color \(a\). By the definition of the refined diagrams, \(e\) appears in \(\mathsf{CVD}^*_k(S)\) if and only if \(a\) is the unique \(k\)-th nearest color of the points in \(e\). Thus, it appears in exactly \(1\) refined diagram. ◻

Proof. First, consider the bichromatic edges of \(\mathsf{CVD}^*_k(S)\). By Lemma [lem:overlay95CVDk95star], these are exactly the edges of \(\mathsf{CVD}_k(S)\) and of \(\mathsf{CVD}_{k-1}(S)\). It follows from Lemma [lem:basics95edge] and the general position assumption, that a point \(x\) on an edge \(e\) of \(\mathsf{CVD}_{k}(S)\) (resp. \(\mathsf{CVD}_{k-1}(S)\)) lies on the common boundary of two regions \(\mathrm{R}_k(H, S)\) and \(\mathrm{R}_k(H', S)\) (resp. \(\mathrm{R}_{k-1}(H, S)\) and \(\mathrm{R}_{k-1}(H', S)\)). By Lemma [lem:neighboring-regions], such an edge \(e\) is a portion of the bisector \(J({a},{a'})\) of the colors \(a \in H \setminus H'\) and \(a' \in H' \setminus H\). For a point \(x\) near \(e\) contained in \(\mathrm{R}_k(H, S)\) (resp. \(\mathrm{R}_{k-1}(H, S)\)), \(a\) and \(a'\) are the \(k\)-th and \((k{+}1)\)-th nearest colors (resp. \((k{-}1)\)-th and \(k\)-th) with respect to \(\preccurlyeq_x\). Thus, a point \(x\) lying on an edge of \(\mathsf{CVD}_{k}(S)\) (resp. \(\mathsf{CVD}_{k-1}(S)\)) implies \(a \sim_x a'\), where \(a = a_k\) and \(a' = a_{k+1}\) (resp. \(a = a_{k-1}\) and \(a' = a_{k}\)). Conversely, if these equivalence conditions hold at \(x\), any sufficiently small neighborhood of \(x\) intersects both adjacent regions, thus \(x\) must lie on their common boundary.

Next, consider a monochromatic edge \(e\) of \(\mathsf{CVD}^*_k(S)\), which is a monochromatic edge of \(\mathsf{FCVD}^*(S_H) \cap \mathrm{R}_k(H, S)\), \(H \subseteq K\). Furthermore, \(e\) lies strictly inside the region \(\mathrm{FR}(a, S_H)\) for some \(a \in H\). A point \(x\) is contained in \(\mathrm{R}_k(H, S) \cap \mathrm{FR}(a, S_H)\) if \(H\) is the set of \(k\) nearest colors from \(x\) and \(a\) is the unique farthest color in \(H\) with respect to \(\preccurlyeq_x\), implying that \(a = a_k\) and \(a_{k-1} \prec_x a_k \prec_x a_{k+1}\). A 1-chromatic edge \(e\) of \(\mathsf{FCVD}^*(S_H)\) inside \(\mathrm{FR}(a, S_H)\) is a portion of an edge of \(\mathsf{VD}(S_a)\). Under the general position assumption, \(x\) lying on an edge of \(\mathsf{VD}(S_a)\) means that \(x\) lies on the bisector \(J({p_j},{p_{j+1}})\) of the nearest sites \(p_j, p_{j+1} \in S_a\) with respect to \(\leqslant_x\). Therefore, \(p_j =_x p_{j+1}\) such that no \(p_i\) for \(i<j\) belongs to \(S_{a_k}\). The converse holds analogously: the strict color order ensures that the neighborhood around \(x\) is contained in \(\mathrm{R}_k(H, S)\), while the site equivalence implies it must lie on the bisector \(J({p_j},{p_{j+1}})\). ◻

Proof. First, consider the \(3\)-chromatic vertices of \(\mathsf{CVD}^*_k(S)\). By Lemma [lem:overlay95CVDk95star], these are exactly the vertices of \(\mathsf{CVD}_k(S)\) and \(\mathsf{CVD}_{k-1}(S)\). Recall from the proof of Lemma [lem:vertex95characterization] that \(x\) is a new vertex of \(\mathsf{CVD}_k(S)\) (resp. \(\mathsf{CVD}_{k-1}(S)\)) if \(a_k \sim_x a_{k+1} \sim_x a_{k+2}\) (resp. \(a_{k-1} \sim_x a_k \sim_x a_{k+1}\)), and \(x\) is an old vertex if \(a_{k-1} \sim_x a_k \sim_x a_{k+1}\) (resp. \(a_{k-2} \sim_x a_{k-1} \sim_x a_k\)). Thus, if \(x\) is a \(3\)-chromatic vertex then \(a_l \sim_x a_{l+1} \sim_x a_{l+2}\) for some \(l \in \{k-2, k-1, k\}\). The reverse implication can be proved analogously, as these equivalences imply the neighborhood of \(x\) intersects the three regions, defining a vertex.

Next, consider the \(2\)-chromatic vertices of \(\mathsf{CVD}^*_k(S)\), which must lie on the \(2\)-chromatic edges of \(\mathsf{CVD}^*_k(S)\). By Lemma [lem:edge95types], if a point \(x\) is on a \(2\)-chromatic edge of \(\mathsf{CVD}^*_k(S)\), then \(a_l \sim_x a_{l+1}\) for some \(l \in \{k-1, k\}\), and thus \(x \in J({a_l},{a_{l+1}})\). Since \(x\) is a vertex of \(J({a_l},{a_{l+1}})\), it is a vertex of \(\mathsf{VD}(S_{a_l} \cup S_{a_{l+1}})\) whose three nearest sites in \(S_{a_l} \cup S_{a_{l+1}}\), with respect to \(\leqslant_x\), include at least one site of color \(a_l\) and one of color \(a_{l+1}\). Under the general position assumption, a point \(x\) being a vertex of \(\mathsf{VD}(S_{a_l} \cup S_{a_{l+1}})\) implies it is equidistant to three sites \(p_j =_x p_{j+1} =_x p_{j+2}\) that are the nearest in \(S_{a_l} \cup S_{a_{l+1}}\) with respect to \(\leqslant_x\). Hence, \(p_j =_x p_{j+1} =_x p_{j+2}\) such that no \(p_i\) for \(i<j\) belongs to \(S_{a_l} \cup S_{a_{l+1}}\). Conversely, satisfying these equivalences implies that \(x\) lies on the common intersection of the three related bisecting curves.

Finally, consider the \(1\)-chromatic vertices of \(\mathsf{CVD}^*_k(S)\). As with the \(1\)-chromatic edges from Lemma [lem:edge95types], a \(1\)-chromatic vertex \(x\) has a unique \(k\)-th nearest color \(a_k\), so \(a_{k-1} \prec_x a_k \prec_x a_{k+1}\), and \(x\) is a vertex of \(\mathsf{VD}(S_{a_k})\). Under the general position assumption, being a vertex of \(\mathsf{VD}(S_{a_k})\) means \(x\) is equidistant from three sites \(p_j =_x p_{j+1} =_x p_{j+2}\) that are the nearest in \(S_{a_k}\) with respect to \(\leqslant_x\). Thus, no \(p_i\) for \(i<j\) belongs to \(S_{a_k}\). For the converse, the strict color ordering guarantees the neighborhood of \(x\) lies strictly inside the region where \(a_k\) is the \(k\)-th nearest color, while the site equivalence implies it is a vertex of the nearest-site Voronoi diagram. ◻

Proof. The quantities \(\sum_{c} v_{c,1}(S')\) and \(\sum_c u_{c,1}(S')\) count the vertices and the unbounded edges, respectively, of the nearest Voronoi diagram \(\mathsf{CVD}^*_1(S')=\mathsf{VD}(S')\). The quantities \(\sum_{c} \bar{v}_{c,1}(S')\) and \(\sum_c \bar{u}_{c,1}(S')\) count the vertices and the unbounded edges, respectively, of the farthest Voronoi diagram \(\overline{\mathsf{CVD}}^*_1(S') = \mathsf{FVD}(S')\). Every region of \(\mathsf{VD}(S')\) is nonempty and simply connected [30] and every vertex is of degree three by the general position assumption. Euler’s formula thus implies the first equation. Every region of \(\mathsf{FVD}(S')\) is unbounded and \(\mathsf{FVD}(S')\) forms a tree [5], [39]. So, Euler’s formula together with the general position assumption implies the second equation. ◻

Proof. Following [28], we first build two ordinary CS-structures for Voronoi vertices.

Let \(\mathcal{V}= \mathcal{V}(S)\) be the set of all Voronoi vertices created by any triplet of sites, i.e., vertices of \(\mathsf{VD}(\{p,q,r\})\) for any three distinct sites \(p,q,r\in S\), regardless of colors. Recall that there are at most two possible Voronoi vertices for each triplet of sites [30]. The set \(\mathcal{V}\) is the set of configurations. Consider two conflict relations \(\chi, \bar{\chi} \subseteq S \times \mathcal{V}\) defined as follows: for each \(p\in S\) and \(v\in \mathcal{V}\) whose defining sites are \(q_1,q_2, q_3\in S\), \[(p,v) \in \chi~\text{iff}~p <_v q_1 =_v q_2 =_v q_3 \quad\text{and}\quad (p,v) \in \bar{\chi}~\text{iff}~q_1 =_v q_2 =_v q_3 <_v p.\] The set systems \((S, \mathcal{V}, \chi)\) and \((S, \mathcal{V}, \bar{\chi})\) are CS-structures.

We then consider the color assignment \(\kappa \colon S \to K\) and derive two color-augmented CS-structures. Let \(\chi_\kappa, \bar{\chi}_\kappa \subseteq K \times \mathcal{V}\) be the corresponding color conflict relations with the following property: for each color \(a\in K\) and \(v\in\mathcal{V}\) defined by three sites \(q_1, q_2, q_3 \in S\), \[(a, v) \in \chi_\kappa~\text{iff}~a \prec_v \kappa(q_1) \sim_v \kappa(q_2) \sim_v \kappa(q_3) \;\text{and}\; (a, v) \in \bar{\chi}_\kappa~\text{iff}~a \mathrel{\overline{\succ}}_v \kappa(q_1) \mathrel{\overline{\sim}}_v \kappa(q_2) \mathrel{\overline{\sim}}_v \kappa(q_3).\]

By Lemma [lem:vertex95types], \(v\) is a new \(c\)-chromatic vertex of \(\mathsf{CVD}^*_{k}(S)\) if and only if \(v\) is a colored configuration induced by \((S, \mathcal{V}, \chi)\) such that \(v\) is in conflict with exactly \(k-1\) colors and \(c\) is equal to the number of distinct colors of the three sites defining \(v\). Analogously, \(v\) is a new \(c\)-chromatic vertex of \(\overline{\mathsf{CVD}}^*_{k}(S)\) if and only if \(v\) is a colored configuration induced by \((S, \mathcal{V}, \bar{\chi})\) such that \(v\) is in conflict with exactly \(k-1\) colors and \(c\) is equal to the number of distinct colors of three sites defining \(v\). Hence, the two color-augmented structures describe the new vertices of \(\mathsf{CVD}^*_k(S)\) and \(\overline{\mathsf{CVD}}^*_k(S)\).

Similarly, we can build two CS-structures encoding the new unbounded edges of \(\mathsf{CVD}^*_k(S)\) and of \(\overline{\mathsf{CVD}}^*_k(S)\). Recall the closed simple curve \(\Gamma\) enclosing \(\mathsf{CVD}^*_k(S)\) and \(\overline{\mathsf{CVD}}^*_k(S)\), defined in Section ¿sec:subsec:perm?. Let \(\mathcal{U} = \mathcal{U}(S)\) be the set of all intersection points between the bisectors in \(\mathcal{J}\) and \(\Gamma\). In this case, the set \(\mathcal{U}\) is the set of configurations. Each configuration \(u\in\mathcal{U}\) is defined by a unique pair of sites.

Consider two conflict relations \(\chi', \bar{\chi}' \subseteq S \times \mathcal{U}\): for each \(p\in S\) and \(u\in \mathcal{U}\) defined by \(q_1, q_2\in S\), \[(p,u) \in \chi'~\text{iff}~p <_u q_1 =_u q_2 \quad\text{and}\quad (p,u) \in \bar{\chi}'~\text{iff}~q_1 =_u q_2 <_u p.\] The set systems defined by the triplets \((S, \mathcal{U}, \chi')\) and \((S, \mathcal{U}, \bar{\chi}')\) form two CS-structures. The corresponding colored configurations induced by the color assignment \(\kappa\) for \(S\) describe the new \(c\)-chromatic unbounded edges in \(\mathsf{CVD}^*_k(S)\) and \(\overline{\mathsf{CVD}}^*_k(S)\), respectively. Specifically, let \(\chi'_\kappa, \bar{\chi}'_\kappa\) be the color-conflict relations corresponding to \(\chi'\) and \(\bar{\chi}'\), respectively. For each \(a\in K\) and \(u\in\mathcal{U}\) defined by two sites \(q_1, q_2 \in S\), \[(a, u) \in \chi'_\kappa~\text{iff}~a \prec_u \kappa(q_1) \sim_u \kappa(q_2) \quad\text{and}\quad (a, u) \in \bar{\chi}'_\kappa~\text{iff}~a \mathrel{\overline{\succ}}_u \kappa(q_1) \mathrel{\overline{\sim}}_u \kappa(q_2).\] By Lemma [lem:edge95types], we observe that a \(c\)-chromatic unbounded edge \(e\) in \(\mathsf{CVD}^*_{k}(S)\) is new if and only if the configuration \(u = e \cap \Gamma\) is in conflict with exactly \(k-1\) colors and \(c\) is equal to the number of distinct colors of the two sites defining \(u\). Analogously, \(u = e \cap \Gamma\) is a new \(c\)-chromatic unbounded edge of \(\overline{\mathsf{CVD}}^*_{k}(S)\) if and only if \(u\) is in conflict with exactly \(k-1\) colors and \(c\) is equal to the number of distinct colors of the two sites defining \(u\). Hence, the two color-augmented structures describe the new unbounded edges of the refined diagrams \(\mathsf{CVD}^*_k(S)\) and \(\overline{\mathsf{CVD}}^*_k(S)\).

From the lower bound lemma [28] (see also [34]), we have the following: For any integer \(1\leqslant r \leqslant m\) and a random subset \(R\subseteq K\) of \(r\) colors, \[\binom{m}{r} \mathop{\mathrm{\mathbf{E}}}[v_{c,1}(S_R)] = \sum_{j=0}^{m-c} v_{c,j+1}\binom{m-c-j}{r-c} \,\text{and}\, \binom{m}{r} \mathop{\mathrm{\mathbf{E}}}[\bar{v}_{c,1}(S_R)] = \sum_{j=0}^{m-c} \bar{v}_{c,j+1}\binom{m-c-j}{r-c}\] for each \(c \in \{1,2,3\}\), where \(S_R = \bigcup_{a\in R} S_a\), and \[\! \binom{m}{r} \mathop{\mathrm{\mathbf{E}}}[u_{c,1}(S_R)] = \sum_{j=0}^{m-c} u_{c,j+1}\binom{m-c-j}{r-c} \,\text{and}\, \binom{m}{r} \mathop{\mathrm{\mathbf{E}}}[\bar{u}_{c,1}(S_R)] = \sum_{j=0}^{m-c} \bar{u}_{c,j+1}\binom{m-c-j}{r-c}\] for each \(c\in\{1,2\}\). Hence, on one hand, we have \[\binom{m}{r}\left(\sum_{c=1}^3 \mathop{\mathrm{\mathbf{E}}}[v_{c,1}(S_R)] + \sum_{c=1}^2 \mathop{\mathrm{\mathbf{E}}}[u_{c,1}(S_R)]\right) = \sum_{c=1}^3 \sum_{j=0}^{m-c} (v_{c,j+1}+u_{c,j+1})\binom{m-c-j}{r-c}\] and \[\binom{m}{r}\left(\sum_{c=1}^3 \mathop{\mathrm{\mathbf{E}}}[\bar{v}_{c,1}(S_R)] - \sum_{c=1}^2 \mathop{\mathrm{\mathbf{E}}}[\bar{u}_{c,1}(S_R)]\right) = \sum_{c=1}^3 \sum_{j=0}^{m-c} (\bar{v}_{c,j+1}-\bar{u}_{c,j+1})\binom{m-c-j}{r-c},\] where we define \(u_{3,j} = \bar{u}_{3,j} = 0\) for all \(j\).

On the other hand, the upper bound lemma [28], together with Lemma [lem:v095u0], implies that \[\begin{align} \binom{m}{r}\left(\sum_{c=1}^3 \mathop{\mathrm{\mathbf{E}}}[v_{c,1}(S_R)] + \sum_{c=1}^2 \mathop{\mathrm{\mathbf{E}}}[u_{c,1}(S_R)]\right) &= \sum_{\substack{R'\subseteq K\\ |R'| = r}}\sum_{c=1}^3 (v_{c,1}(S_{R'}) + u_{c,1}(S_{R'})) \\ &= \sum_{R'} (2|S_{R'}| - 2) \\ & = 2\binom{m-1}{r-1}n - 2\binom{m}{r}, \end{align}\] for any \(2\leqslant r\leqslant m\). Similarly, we also have \[\binom{m}{r}\left(\sum_{c=1}^3 \mathop{\mathrm{\mathbf{E}}}[\bar{v}_{c,1}(S_R)] - \sum_{c=1}^2 \mathop{\mathrm{\mathbf{E}}}[\bar{u}_{c,1}(S_R)]\right) = - 2\binom{m}{r},\] for any \(2\leqslant r\leqslant m\).

These two sets of equations for \(2\leqslant r\leqslant m\) form two systems of linear equations, which are analogous to those in [28]. So, letting \[\begin{align} V_k := v_{3,k} + \sum_{j=1}^k (v_{2,j} + (k-j+1) v_{1,j}), \qquad & \overline{V}_k := \bar{v}_{3,k} + \sum_{j=1}^k (\bar{v}_{2,j} + (k-j+1) \bar{v}_{1,j}), \\ U_k := \sum_{j=1}^k (u_{2,j} + (k-j+1) u_{1,j}), \quad\text{and}\quad & \overline{U}_k := \sum_{j=1}^k (\bar{u}_{2,j} + (k-j+1) \bar{u}_{1,j}), \end{align}\] we obtain \[V_k + U_k = k(2n-k-1) \quad\text{and}\quad \overline{V}_k - \overline{U}_k = -k(k+1),\] for each \(1\leqslant j \leqslant m-1\). From Lemma [lem:consecutive95orders], for each \(1\leqslant k\leqslant m-1\), we know that the numbers of vertices of \(\mathsf{CVD}_k(S)\) and of \(\overline{\mathsf{CVD}}_k(S)\) are equal to \[v_{3,k} + v_{3,k-1} + v_{2,k} \quad\text{and}\quad \bar{v}_{3,k} + \bar{v}_{3,k-1} + \bar{v}_{2,k},\] respectively, where \(v_{3, 0} = \bar{v}_{3, 0} = 0\). Therefore, the claimed equations are derived analogously to [28]. ◻

Proof. By Lemma [lem:complexity], the number of vertices in \(\mathsf{CVD}_k(S)\) is \[2k(2n-k) - 2n - U_k - U_{k-1} - 2\sum_{j=1}^{k-1} v_{2,j} - \sum_{j=1}^k(2k-2j+1)v_{1,j} \leqslant 4k(n-k) - 2n\] since \(U_k \geqslant k(k+1)\) as shown in Lemma [lem:sumU]. The number of vertices in \(\overline{\mathsf{CVD}}_k(S)\) is \[\overline{U}_k + \overline{U}_{k-1} - 2k^2 - 2\sum_{j=1}^{k-1} v_{2,j} - \sum_{j=1}^k(2k-2j+1)v_{1,j} \leqslant 4k(n-k) - 2n\] since \(\overline{U}_k \leqslant k(2n-k-1)\) as shown in Lemma [lem:sumU].

The tightness of the upper bound \(4k(n-k)-2n\) follows from the tightness of the bounds in Lemma [lem:sumU] and the fact that the number of \(c\)-chromatic vertices, \(c<3\), is zero if \(n=m\). ◻

Proof. Recall the CS-structure \((S, \mathcal{V}, \chi)\) from the proof of Lemma [lem:complexity], where the set of configurations \(\mathcal{V}\) is the set of all possible Voronoi vertices, and the conflict relation \(\chi \subseteq S \times \mathcal{V}\) is defined such that a vertex \(v\in \mathcal{V}\) is in conflict with a site \(p \in S\) if and only if \(v\) is nearer to \(p\) than to the three sites defining \(v\). Recall also the color-augmented structure \((S, \mathcal{V}, \chi_\kappa)\), where \(\chi_\kappa \subseteq K \times \mathcal{V}\) is defined such that a \(c\)-chromatic vertex \(v\) is in conflict with a color \(a \in K\) if and only if \(v\) is nearer to \(a\), with respect to the minimal dominance \(\preccurlyeq_v\), than to the \(c\) colors of the sites defining \(v\).

We define a new color conflict relation \(\chi''_\kappa \subseteq K \times \mathcal{V}\) that is appropriate for large values of \(k\). For each color \(a \in K\) and vertex \(v \in \mathcal{V}\) defined by three sites \(q_1, q_2, q_3 \in S\): \[(a, v) \in \chi''_\kappa~\text{iff}~\kappa(q_1) \sim_v \kappa(q_2) \sim_v \kappa(q_3) \prec_v a.\] We call \(\{\kappa(q_1),\kappa(q_2),\kappa(q_3)\}\) the defining colors of the color configuration \(v\).

Let \(r = m-k+1\). The number of conflicts of a color configuration \(v\) with respect to \(\chi''_\kappa\) is the number of colors farther from \(v\) than its defining colors. A new \(c\)-chromatic vertex \(v\) of \(\mathsf{CVD}^*_k(S)\) has \(c\) defining colors, and \(k-1\) other colors closer than the defining colors; therefore, \(v\) has \(m-c-(k-1) = r-c\) colors farther from its defining colors. Let \(v''_{c,r-c+1}\) denote the number of \(c\)-chromatic vertices that are in conflict with exactly \(r-c\) colors with respect to \(\chi''_\kappa\). Note that \(v_{c,k} = v''_{c,r-c+1}\). From Lemma [lem:consecutive95orders], it follows that the total number of vertices in \(\mathsf{CVD}^*_k(S)\) is equal to \[\begin{align} {6} & v_{1,k} && + v_{2,k} && + v_{2,k-1} && + v_{3,k} && + v_{3,k-1} && + v_{3,k-2} \\ = \quad & v''_{1,r} && + v''_{2,r-1} && + v''_{2,r} && + v''_{3,r-2} && + v''_{3,r-1} && + v''_{3,r} \end{align}\] where \(v''_{3,-1} = v''_{3,0} = v''_{2,0} = 0\).

Assuming that \(\mathsf{FCVD}(S)\) has linear complexity, it follows that \(\sum_c v''_{c,1} = O(n)\). Note that for \(c=1\), the total number of monochromatic vertices is \(\sum_{r} v''_{1,r} = O(n)\). Theorem 4 in [28] applies to any color-augmented CS-structure, so it also applies to \((S,\mathcal{V},\chi''_\kappa)\). Let \(|\mathcal{F}_{c,j}(S, \chi''_\kappa)|\) denote the number of \(c\)-chromatic configurations that are in conflict with exactly \(j\) colors; observe that \(v''_{c,j+1} = |\mathcal{F}_{c,j}(S, \chi''_\kappa)|\). Applying the theorem with the function \(T_0(x)=x\) (since the complexity is linear for \(j=0\) and any \(S' \subseteq S\)), for each \(c \in \{2,3\}\) and \(1 \leqslant r \leqslant\lfloor m/c \rfloor\), the number of \(c\)-chromatic vertices with at most \(r-1\) conflicts is \[\sum_{j=0}^{r-1} v''_{c,j+1} = \sum_{j=0}^{r-1} |\mathcal{F}_{c,j}(S, \chi''_\kappa)| = O\left(\frac{r^c}{m} \cdot T_0\left(\frac{mn}{r}\right)\right) = O\left(\frac{r^c}{m} \cdot \frac{mn}{r}\right) = O(r^{c-1} n).\] Thus, the sum \(\sum_{j=0}^{r-1} v''_{c,j+1}\) for all \(c\in\{1,2,3\}\) is bounded by \(O(n + r n + r^2 n)\). Substituting \(r = m - k + 1\), the combinatorial complexity of \(\mathsf{CVD}_{k}^*(S), \ldots, \mathsf{CVD}_{m}^*(S)\) for \(\lceil \frac{2m}{3} \rceil +1 \leqslant k\leqslant m-1\) is \(O((m-k)^2 n)\).

Similarly, we define the color conflict relation \(\bar{\chi}''_\kappa \subseteq K \times \mathcal{V}\) for each color \(a \in K\) and vertex \(v \in \mathcal{V}\) defined by three sites \(q_1, q_2, q_3 \in S\): \[(a, v) \in \bar{\chi}''_\kappa~\text{iff}~\kappa(q_1) \mathrel{\overline{\sim}}_v \kappa(q_2) \mathrel{\overline{\sim}}_v \kappa(q_3) \mathrel{\overline{\succ}}_v a.\] The bound on \(\overline{\mathsf{CVD}}_{k}^*(S), \ldots, \overline{\mathsf{CVD}}_{m}^*(S)\) follows analogously. ◻

Proof. The proof is done by establishing one-to-one correspondences between:

• The set of new monochromatic unbounded edges of \(\mathsf{CVD}^*_k(S)\) and the set of monochromatic switches at position \(k\) in \(\Lambda(\Pi(S))\).

• The set of new bichromatic unbounded edges of \(\mathsf{CVD}^*_k(S)\) and the set of bichromatic switches at position \(k\) in \(\Lambda(\Pi(S))\).

• The set of new monochromatic unbounded edges of \(\overline{\mathsf{CVD}}^*_k(S)\) and the set of monochromatic switches at position \(k\) in \(\Lambda(\overline{\Pi}(S))\).

• The set of new bichromatic unbounded edges of \(\overline{\mathsf{CVD}}^*_k(S)\) and the set of bichromatic switches at position \(k\) in \(\Lambda(\overline{\Pi}(S))\).

Let \(x \in \Gamma\), and let \(a_1 \preccurlyeq_x \cdots \preccurlyeq_x a_m\) and \(p_1 \leqslant_x \cdots \leqslant_x p_n\) be the ordering of colors in \(K\) with respect to \(\preccurlyeq_x\) and the ordering of sites in \(S\) with respect to \(\leqslant_x\), respectively.

Suppose that it holds that \(a_{k-1} \prec_x a_k \prec_x a_{k+1}\) and \(p_{j-1} <_x p_j =_x p_{j+1} <_x p_{j+2}\) for some \(j\) such that \(p_j, p_{j+1} \in S_{a_k}\), and \(p_i \notin S_{a_k}\) for all \(i<j\). Then \(p_j, p_{j+1}\) are the nearest sites among those in \(S_{a_k}\) at \(x\). Thus, \(x = e\cap \Gamma\) for a new monochromatic unbounded edge \(e\) of \(\mathsf{CVD}^*_k(S)\) (see also Lemma [lem:edge95types]). At the same time, \(x \in \Gamma\) corresponds to the switch \(\sigma\) of \(p_j\) and \(p_{j+1}\) between two consecutive permutations \(\pi_i,\pi_{i+1} \in \Pi(S)\). As both \(p_j\) and \(p_{j+1}\) belong to the same color \(S_{a_k}\) and \(a_k\) is the \(k\)-th nearest color locally near \(x\), the switch \(\sigma\) is monochromatic happening at position \(k\) by which the leader of color \(a_k\) is replaced between \(\lambda_i\) and \(\lambda_{i+1}\). Conversely, any monochromatic switch of \(p_j\) and \(p_{j+1}\) of color \(a_k\) happening at position \(k\) corresponds to a point \(x\in \Gamma\) that satisfies the above condition. This establishes the first one-to-one correspondence between the set of new monochromatic unbounded edges of \(\mathsf{CVD}^*_k(S)\) and the set of monochromatic switches at position \(k\) in \(\Lambda(\Pi(S))\), implying that the number of monochromatic switches at position \(k\) in \(\Lambda(\Pi(S))\) is exactly \(u_{1,k}\).

Next, if it holds that \(a_{k-1} \prec_x a_k \sim_x a_{k+1} \prec_x a_{k+2},\) then \(x \in \mathop{\mathrm{cl}}\mathrm{R}_k(H, S) \cap \mathop{\mathrm{cl}}\mathrm{R}_k(H',S)\) for \(H = \{a_1, \ldots, a_k\}\) and \(H' = H \cup \{a_{k+1}\} \setminus \{a_{k}\}\). Thus \(x = e \cap \Gamma\) for a new bichromatic unbounded edge \(e\) of \(\mathsf{CVD}^*_k(S)\) (see Lemma [lem:edge95types]). At the same time, \(x\) corresponds to the switch of the leaders of two colors \(a_k\) and \(a_{k+1}\) between two consecutive sequences \(\lambda_i\) and \(\lambda_{i+1}\) of color leaders, so a bichromatic switch at position \(k\). Conversely, for any bichromatic switch at position \(k\) corresponding to a point \(x\in\Gamma\), we have the same condition as above at \(x\), so \(x\) lies on a new bichromatic unbounded edge of \(\mathsf{CVD}^*_k(S)\). This implies that the number of bichromatic switches at position \(k\) in \(\Lambda(\Pi(S))\) is equal to \(u_{2,k}\).

The other two cases for the maximal diagrams \(\overline{\mathsf{CVD}}^*_k(S)\) can be shown analogously using the sequence \(\overline{\Pi}(S)\) of reversed permutations. Let \(\bar{\lambda}_i\) be the sequence of color leaders induced from the reversed permutation \(\bar{\pi}_i\) such that \(\Lambda(\overline{\Pi}(S)) = (\bar{\lambda}_0, \ldots, \bar{\lambda}_{N-1}, \bar{\lambda}_N=\bar{\lambda}_0)\). Notice that the \(k\)-th farthest color with respect to the maximal dominance \(\mathrel{\overline{\succcurlyeq}}_x\) is at position \(k\) in the corresponding color-leader sequence \(\bar{\lambda}_i\). Hence, the characterization of new edges of \(\overline{\mathsf{CVD}}^*_k(S)\), analogous to Lemma [lem:edge95types], implies the last two correspondences between new unbounded edges of \(\overline{\mathsf{CVD}}^*_k(S)\) and switches at position \(k\) in \(\Lambda(\overline{\Pi}(S))\). Consequently, the number of monochromatic switches at position \(k\) in \(\Lambda(\overline{\Pi}(S))\) is equal to \(\bar{u}_{1,k}\), while the number of bichromatic switches at position \(k\) in \(\Lambda(\overline{\Pi}(S))\) is equal to \(\bar{u}_{2,k}\). ◻

Proof. If \(k < \rho^*(a)\), then \(\max \{k + 1 - \rho^*(a), 0\} = 0\) and the inequality holds trivially, so assume \(k \geqslant\rho^*(a)\).

We first observe that there are at least two changes of \(\lambda_i(a)\) over \(0\leqslant i\leqslant N-1\). This is obvious from the fact that \(\lambda_i(a)\) is the first element of the subsequence of \(\pi_i\) that contains those elements in \(\{1, \ldots, n\}\) whose color is \(a\) and the property (P2) that every pair of elements switches exactly twice.

Consider any two such changes happened at \(0\leqslant i_1 < i_2 < N\), and let \(j_1:=\rho_{i_1}(a)\) and \(j_2:=\rho_{i_2}(a)\) be two positions of the leader of \(a\) in \(\lambda_{i_1}\) and \(\lambda_{i_2}\), respectively. By definition, we have \(j_1, j_2 \leqslant\rho^*(a) \leqslant k\). Thus, we obtain \[\sum_{j=1}^k (k-j+1) \mu_a(j) \geqslant(k-j_1+1) + (k-j_2+1) \geqslant 2 (k - \rho^*(a) +1)\] by the existence of two changes of \(\lambda_i(a)\). ◻

Proof. Recall our assumption that the leader of color \(a\) is placed at position \(a\) in \(\lambda_0\), that is, \(\rho_0(a) = a\). If \(\hat{k}_a < a - 1\), then the inequality holds trivially, so assume that \(\hat{k}_a \geqslant a\).

Let \(z\) be an index such that \(\rho_z(a) = \hat{k}_a + 1\), and let \[A := \{ a'\in K \mid a' > a~\text{and}~\rho_z(a') < \rho_z(a) = \hat{k}_a+1 \}.\] be the set of colors \(a' > a\) preceding \(a\) in \(\lambda_z\). Since the order between colors \(a\) and each \(a' \in A\) is reversed between \(\lambda_0\) and \(\lambda_z\), there must be at least \(|A|\) many bichromatic switches while we move from \(\lambda_0\) to \(\lambda_z\), counted in \(\sum_{j=1}^{\hat{k}_a} \beta_a(j)\). On the other hand, while we move from \(\lambda_z\) to \(\lambda_N = \lambda_0\), this order between \(a\) and each \(a'\in A\) should be reversed again. This implies that \[\sum_{j=1}^k \beta_a(j) \geqslant\sum_{j=1}^{\hat{k}_a} \beta_a(j) \geqslant 2|A|.\]

To bound \(|A|\), let \(B := \{ a'\in K \mid a' < a~\text{and}~\rho_z(a') < \rho_z(a)\}\). Obviously, \(|B| \leqslant a-1\) and \(A\cap B =\emptyset\). Since \(A\cup B\) consists of all colors \(a'\) such that \(\rho_z(a') < \rho_z(a) = \hat{k}_a + 1\), we have \(|A\cup B| = \hat{k}_a\) and hence \[|A| = |A\cup B| - |B| \geqslant\hat{k}_a - (a - 1) = \hat{k}_a + 1 - a,\] implying the inequality. ◻

Proof. Let \(t \in\{1, \ldots, n\}\) be the only element of color \(a\), so \(t\) is always the leader of \(a\): \(\lambda_i(a) = t\) for all \(i\). Since every pair of elements switch exactly twice in the sequence \(\Pi\) (condition (P2)), \(t\) is involved in at least two bichromatic switches with each of the other colors. Among them, those switches with \(a' > a\) are counted in \(\sum_j \beta_a(j)\), so we have \[\sum_j \beta_a(j) = \sum_{j=1}^{\rho^*(a)} \beta_a(j) \geqslant 2(m-a).\]

We have two cases: whether \(k \geqslant\rho^*(a)\) or \(k < \rho^*(a)\). If \(k \geqslant\rho^*(a)\), then we have \[\sum_{j=1}^{k} \beta_a(j) \geqslant\sum_{j=1}^{\rho^*(a)} \beta_a(j) \geqslant 2 (m - a) \geqslant\max\{2 ( k + 1 - a ), 0\}\] since \(k \leqslant m-1\). Otherwise, if \(k < \rho^*(a)\), then Lemma [lem:bi95ineq] is strong enough to conclude the lemma: \[\sum_{j=1}^k \beta_a(j) \geqslant\max\{2 ( \hat{k}_a + 1 - a ), 0\} \geqslant\max\{2 ( k + 1 - a ), 0\}\] since \(\hat{k}_a = \min\{k, \rho^*(a) - 1\} = k\). ◻

Proof. If there is only one element in \(\{1, \ldots, n\}\) whose color is \(a\), then \(\mu_a(j) = 0\) for all \(j\), so Lemma [lem:bi95ineq95195site] implies the lemma. So, in the following, we assume that there are at least two elements whose color is \(a\).

Adding the inequalities of Lemmas [lem:mc95ineq95295sites] and [lem:bi95ineq] yields \[\sum_{j=1}^{k} \beta_a(j) + \sum_{j=1}^{k} (k-j+1)\mu_a(j) \geqslant\max\{2 (\hat{k}_a + 1 - a), 0\} + \max\{2 ( k + 1 - \rho^*(a) ), 0\}.\]

We simplify the right-hand side by a case analysis on \(\hat{k}= \min\{k, \rho^*(a)-1\}\). If \(\rho^*(a) \leqslant k\), then \(\hat{k}_a = \rho^*(a)-1\) and \(\hat{k}_a + 1 - a = \rho^*(a) - a\). Note also the trivial fact that \(\rho^*(a) - a = \rho^*(a) - \rho_0(a) \geqslant 0\). So, the right-hand side is simplified to \[2(\rho^*(a)-a) + \max\{2(k-\rho^*(a)+1),0\} = \max\{2(k + 1 - a), 0\}.\] Otherwise, if \(\rho^*(a) > k\), then \(\hat{k}_a = k\) and \(\max\{2 ( k + 1 - \rho^*(a)), 0\} = 0\). So, we have \[\max\{2 (\hat{k}_a + 1 - a), 0\} + \max\{2 ( k + 1 - \rho^*(a) ), 0\} = \max\{2 ( k + 1 - a ), 0\},\] as claimed. ◻

Proof. If \(t\) is the only element of color \(a\), then the lemma is trivially true, since \(\lambda_i(a) = t\) for all \(i\) and thus there is no monochromatic switches involving \(t\). So, assume there is at least one more element \(t' < t\) of the same color \(a\). Let \(T_a\) be the set of elements \(t'\) whose colors are commonly \(a\). Consider the subsequence \(\tau_i\) of \(\pi_i\) that contains the elements in \(T_a\). Observe that \(t\) is at the first position in \(\tau_i\) if and only if \(t = \lambda_i(a)\).

Now, suppose that \(t = \lambda_i(a)\) for some \(i\). Since \(t\) is at the last position in the initial permutation \(\tau_0\), in order for \(t\) to step forward to the first position, every other member in \(T_a\) has to be switched with \(t\), and then they have to be switched with \(t\) again by condition (P2) which requires that every pair of elements is switched exactly twice in \(\Pi\). If the second switch between \(t\) and any \(t' \in T\) happens in \(\tau_z\) at some \(0\leqslant z\leqslant N-1\), then \(t'\) precedes \(t\) in \(\tau_i\) for any \(z< i \leqslant N-1\). This proves the lemma. ◻

Proof. If \(t = \lambda_0(a)\) is the initial leader of color \(a\), then there is no other element \(t' < t\) of the same color \(a\). Hence, there is no monochromatic switch contributed to \(\hat{\mu}_t(j)\) for all \(j\). So, we assume that \(t\) is in color \(a\) and there is at least one more element \(t' < t\) of the same color \(a\). Here, we redefine \(T_a\) to be the set of elements \(t' \leqslant t\) whose colors are commonly \(a\), and consider the subsequence \(\tau_i\) of \(\pi_i\) that contains the elements in \(T_a\), as in the proof of Lemma [lem:ms95last]. Observe that any monochromatic switch in \(\Lambda\) involving \(t\) corresponds to a switch between the first and second positions that involves \(t\) in the \(\tau_i\)’s, while the converse is not necessarily true. Hence, we have \(\sum_{j=1}^{m} \hat{\mu}_t(j) \leqslant 2\) by Lemma [lem:ms95last]. ◻

Proof. First, assume that \(t=\lambda_0(a)\) for some color \(a\in K\). Note, by Lemma [lem:bar95mc], that \(\sum_j \hat{\mu}_t(j)=0\), so we are interested in an upper bound of \(\sum_{j=1}^k \hat{\beta}_t(j)\). Let \(T = \{1, \ldots, t\}\) be the set of elements preceding \(t\) in \(\pi_0\), including \(t\). We consider another circular sequence \(\Pi' = (\pi'_0, \ldots, \pi'_{N-1})\) of permutations \(\pi'_i\) of \(T\) such that \(\pi'_i\) is the subsequence of \(\pi_i\) that contains the elements in \(T\). We also let \(\Lambda' = \Lambda(\Pi') = (\lambda'_0, \ldots, \lambda'_{N-1})\) be the sequence of color leaders induced from \(\Pi'\). Note that each bichromatic switch in \(\Lambda\) counted in the sum \(\sum_{j} \hat{\beta}_t(j)\) corresponds to a bichromatic switch in \(\Lambda'\) involving \(t\), since \(t\) is the largest element in \(T\) and we charge each switch in \(\Lambda\) to the larger element of the two involved elements. Hence, it suffices for our purpose to have an upper bound on the number of bichromatic switches involving \(t\) in \(\Lambda'\).

Let \(T_b \subseteq T\) for \(b \in K\) be the set of elements in \(T\) whose color is \(b\). Note that \(T_a = \{t\}\) and \(T_b = \emptyset\) for \(b > a\) by our construction. Pick any color \(b < a\). While we move from \(\pi'_0\) to \(\pi'_{N-1}\), observe that the first bichromatic switch between \(t\) and the leader of color \(b\) can happen after switches between \(t\) and every member \(t'\in T_b\), since \(t\) is at the last position in \(\pi'_0\). If there is the second bichromatic switch between \(t\) and the leader \(t'\) of \(b\), then \(t'\) precedes \(t\) in \(\pi'_i\) afterwards until \(i=N\) by condition (P2), so \(t\) will never make a third bichromatic switch with the leader of color \(b\). Therefore, for each color \(b<a\), \(t\) is involved in at most two bichromatic switches with the leader of \(b\), implying that \[\sum_{j=1}^{m-1} \hat{\beta}_t(j) \leqslant 2(a-1).\]

Now, we consider those switches at position \(k+1\) or larger, that is, those counted in \(\sum_{j=k+1}^{m-1}\hat{\beta}_t(j)\). If \(k \geqslant a\), then it is zero and we get \(\sum_{j=1}^k \hat{\beta}_t(j) \leqslant 2(a-1)\). We then assume \(k < a\). Since the initial position of \(t\) in \(\lambda'_0\) is \(a\), at least \(a - k - 1\) bichromatic switches are necessary for \(t\) to arrive at position \(k\) or smaller. Hence, if \(\hat{\beta}_t(j) \geqslant 1\) for some \(j \leqslant k\), then we have \[\sum_{j=k+1}^{m-1} \hat{\beta}_t(j) \geqslant 2(a-k-1)\] since we need additional \(a-k-1\) switches for \(t\) to return back to the original last position in \(\pi'_N = \pi'_0\). This implies that \[\sum_{j=1}^k \hat{\beta}_t(j) = \sum_{j=1}^{m-1} \hat{\beta}_t(j) - \sum_{j=k+1}^{m-1}\hat{\beta}_t(j) \leqslant 2(a-1) - 2(a-k-1) = 2k.\] Hence, we have \[\sum_{j=1}^k \hat{\beta}_t(j) \leqslant\min\{2(a-1), 2k\}\] if \(t = \lambda_0(a)\) for \(a\in K\).

Next, assume that \(t\) is not the leader of \(a\) in \(\pi'_0\), so \(|T_a| \geqslant 2\). Since \(t\) is the largest element of \(T_a\), the total number of monochromatic switches involving \(t\) in \(\Lambda'\) is either \(0\) or \(2\) by Lemma [lem:ms95last]. In the former case, \(\lambda'_i(a) \neq t\) for all \(i\), so \(\hat{\beta}_t(j) = 0\) for all \(j\). We thus assume the latter case. Observe that the above arguments apply to show the same upper bound \(\sum_{j=1}^k \hat{\beta}_t(j) \leqslant\min\{2(a-1), 2k\}\) in this case as well. In the following, we consider the two monochromatic switches involving \(t\) to obtain the claimed upper bound.

Let \(z_1, z_2\) with \(0\leqslant z_1 < z_2 < N\) and \(j_1, j_2\) with \(1\leqslant j_1, j_2 \leqslant a\) be integers such that the first monochromatic switch involving \(t\) happens at position \(j_1\) of \(\lambda'_{z_1}\) and the second one happens at position \(j_2\) of \(\lambda'_{z_2}\). That is, \(t = \lambda'_i(a)\) for \(z_1\leqslant i < z_2\). While we move from \(\pi'_0\) to \(\pi'_{z_1}\), element \(t\) switches at least \(a-j_1\) leaders of other colors \(b<a\), but none of them are bichromatic switches in \(\Lambda'\), as \(t \neq \lambda_i(a)\) for \(0\leqslant i<z_1\). Analogously, while we move from \(\pi'_{z_2}\) to \(\pi'_N = \pi'_0\), there are at least \(a-j_2\) switches that are not counted as bichromatic switches in \(\Lambda'\). Hence, we have \[\sum_{j=1}^{m-1} \hat{\beta}_t(j) \leqslant 2(a-1) - (a-j_1) - (a-j_2) = j_1 + j_2 - 2.\] By a similar argument as above, if \(j_1 > k\), then we have \(\sum_{j=k+1}^{m-1} \hat{\beta}_t(j) \geqslant j_1 - k - 1\); if \(j_2 > k\), \(\sum_{j=k+1}^{m-1} \hat{\beta}_t(j) \geqslant j_2 - k - 1\); and if both \(j_1 > k\) and \(j_2>k\), then \(\sum_{j=k+1}^{m-1} \hat{\beta}_t(j) \geqslant j_1 + j_2 - 2k - 2\). We thus have \[\sum_{j=1}^k \hat{\beta}_t(j) \leqslant j_1 + j_2 -2 - \max\{j_1 - k -1, 0\} - \max\{j_2-k-1,0\} \leqslant\min\{j_1 - 1, k\} + \min\{j_2 - 1, k\},\] on one hand. On the other hand, we observe that \[\sum_{j=1}^k (k-j+1)\hat{\mu}_t(j) \leqslant\max\{k - j_1 + 1, 0\} + \max\{k - j_2 + 1, 0\}\] since the actual positions at which the monochromatic switches happen in the original leader sequences \(\Lambda\) are not smaller than \(j_1\) and \(j_2\), respectively. Adding these two inequalities, we obtain \[\begin{align} & \sum_{j=1}^k (\hat{\beta}_t(j) + (k-j+1)\hat{\mu}_t(j)) \\ \leqslant& \min\{j_1 - 1, k\} + \min\{j_2 - 1, k\} + \max\{k - j_1 + 1, 0\} + \max\{k - j_2 + 1, 0\}\\ = & \min\{j_1 - 1, k\} + \min\{j_2 - 1, k\} + \max\{-j_1+1, -k\} + \max\{-j_2 + 1, -k\} + 2k\\ = & \min\{j_1 - 1, k\} + \min\{j_2 - 1, k\} - \min\{j_1 - 1, k\} - \min\{j_2 - 1, k\} + 2k = 2k, \end{align}\] as claimed. ◻

Proof. Let \(m\) and \(n\) be any two integers with \(2\leqslant m\leqslant n\). The colors of elements \(\{1, \ldots, n\}\) are assigned as follows: the colors of the first \(m\) elements are all distinct such that the color of \(t\) for \(1\leqslant t\leqslant m\) is \(t\), and the other \(n-m\) elements are colored arbitrarily. Initially, set \(\pi_0 = (1,2, \ldots, n)\). The sequence \(\Pi_{n,m} = (\pi_0, \ldots, \pi_{N-1}, \pi_N = \pi_0)\) is described by a sequence \(\Sigma\) of switches \(\sigma_i\) between two neighboring elements in \(\pi_i\). The sequence \(\Sigma\) is again divided into \(n-1\) blocks, called turns. For each element \(t\in\{1, \ldots, n\}\), the turn of \(1\) is empty, \(\Sigma_1 = \varnothing\); the turn of \(2\) consists of two switches, \(\Sigma_2 = (12, 21)\); the turn of \(3\) consists of four switches, \(\Sigma_3 = (23, 13, 31, 32)\). In general, the turn of \(t\) consists of \(2(t-1)\) switches \[\Sigma_t = ((t-1)t, (t-2)t, \ldots, 2t, 1t, t1, t2 \ldots, t(t-2), t(t-1)).\] Then the whole sequence \(\Sigma\) of switches is the concatenation of these turns in order: \[\Sigma = \Sigma_1, \Sigma_2, \ldots, \Sigma_n.\] It is obvious that the number of switches in \(\Sigma\) is exactly \(N=2\binom{n}{2} = n(n-1)\) and every pair of two elements is switched exactly twice in \(\Pi_{n,m}\).

Observe that the turn of \(t\) moves \(t\) forward to the first position (that is, \(\pi_{(t-1)^2} = (t, 1, 2, \ldots, t-1, t+1, \ldots, n)\)) and then back to its original position, so after each turn we get back to the initial permutation \(\pi_0\) (that is, \(\pi_{t(t-1)} =\pi_0\)). From this observation, the turn of \(t\) makes exactly \(2(a-1)\) bichromatic switches, where \(a\) is the color of \(t\): exactly two at position \(j\) for \(1\leqslant j\leqslant a-1\). In addition, the turn of \(t\) makes exactly two monochromatic switches at position \(a\) if the color of \(t\) is \(a\) and \(\lambda_0(a) \neq t\); if \(t = \lambda_0(a)\), then no monochromatic switch happens. So, the contribution of the turn of \(t\) to \(G_k(\Pi_{n,m})\) is exactly \[\begin{cases} \min\{2(a-1), 2k\} & \text{if}~t=\lambda_0(a)\\ 2k & \text{otherwise}. \end{cases}\] The latter case follows from \(2(a-1)\) bichromatic switches and two monochromatic switches at position \(a\), which contributes an amount of \(2(k - a + 1)\) to \(G_k(\Pi_{n,m})\). Summing this up over all \(t\) gives us \[G_k(\Pi_{n,m}) = k(2n-k-1).\]

The second construction \(\Pi'_{n,m} = (\pi'_0, \ldots, \pi'_{N-1}, \pi'_N =\pi'_0)\) is done in a similar fashion, but with a different sequence \(\Sigma'\) of switches. Set \(\pi'_0 = (1,2, \ldots, n)\), and we color the elements as in the above construction \(\Pi_{n,m}\). The sequence \(\Sigma'\) of switches consists of turns: For each element \(t\in\{1, \ldots, n\}\), the turn of \(t\) is given as \[\Sigma'_t = (t(t+1), t(t+2), \ldots, t(n-1), tn, nt, (n-1)t, \ldots, (t+2)t, (t+1)t ).\] Then the whole sequence \(\Sigma'\) of switches is as follows: \[\Sigma' = \Sigma'_n, \Sigma'_{n-1}, \ldots, \Sigma'_1.\] Observe that the turn of \(t\) moves \(t\) backward to the last position and then back to its original position, so after each turn we get back to the initial permutation \(\pi'_0\).

In this sequence \(\Pi'_{n,m}\), note that every monochromatic switch happens at position \(m\) by construction. Further, observe that the turn of \(t\) for every \(t > k\) makes no switches at position \(j\) for \(j\leqslant k\), neither monochromatic nor bichromatic. For \(t \leqslant k\), the turn of \(t\) makes exactly \(2(k-t+1)\) bichromatic switches at position \(j\) for \(j\leqslant k\). Hence, we have \[G_k(\Pi'_{n,m}) = \sum_{t=1}^k 2(k-t+1) = k(k+1)\] for any \(1\leqslant k\leqslant m-1\).

Note that a more careful analysis can show that any circular sequence \(\Pi\) determined by the sequence \(\Sigma_{n,m}\) (or \(\Sigma'_{n,m}\), resp.) of switches with any arbitrary initial permutation \(\pi_0\) yields the same quantity \(G_k(\Pi) = k(2n-k-1)\) (\(G_k(\Pi) = k(k+1)\), resp.). ◻

Proof. For each \(x \in \Gamma\) that avoids any bisecting curves in \(\mathcal{J}\), let \(\pi(x)\) be the permutation of the sites induced by \(\leqslant_x\). Let \(\bar{\pi}(x)\) be the reverse of the permutation \(\pi(x)\), and let \(\bar{\lambda}(x)\) be the subsequence of \(\bar{\pi}(x)\) that contains the leaders of all colors. Traversing \(\Gamma\) corresponds to iterating through the permutations in \(\overline{\Pi}(S)\); thus, \(\bar{\pi}(x)\) and \(\bar{\lambda}(x)\) appear in \(\overline{\Pi}(S)\) and \(\Lambda(\overline{\Pi}(S))\) as \(\bar{\pi}_i\) and \(\bar{\lambda}_i\), respectively, for some index \(0 \leqslant i \leqslant N-1\). We assume without loss of generality that we traverse \(\Gamma\) clockwise.

First, we compute the monochromatic unbounded edges in \(\overline{\mathsf{CVD}}^*_{\leqslant m}(S)\), which correspond to the unbounded edges in \(\bigcup_{i \in K}\mathsf{FVD}(S_i)\). For each color \(i\), the unbounded edges of \(\mathsf{FVD}(S_i)\) can be computed in \(O(|S_i| \log |S_i|)\) time using a divide-and-conquer algorithm similarly to the farthest segment Voronoi diagram in [42]. Next, we compute the bichromatic unbounded edges in \(\overline{\mathsf{CVD}}^*_{\leqslant m}(S)\) by traversing \(\Gamma\). We select an arbitrary starting point \(x \in \Gamma\) and compute \(\bar{\pi}(x)\) and \(\bar{\lambda}(x)\) in \(O(n \log n)\) time. Let \(x_m\) be the intersection of \(\Gamma\) with the next monochromatic edge encountered during the traversal from \(x\). For each pair of consecutive sites \(p,q\) in \(\bar{\lambda}(x)\), we compute the two intersections between \(J({p},{q})\) and \(\Gamma\). Among these \(2(m-1)\) resulting intersections, let \(x_b\) be the first one we encounter traversing \(\Gamma\) starting from \(x\).

If \(x_b\) precedes \(x_m\) while traversing \(\Gamma\) from \(x\), then \(x_b\) corresponds to the next switch between the leaders of two colors in \(\Lambda(\overline{\Pi}(S))\). Thus, it follows from the proof of Lemma [lem:U-G] that the unbounded edge associated with \(x_b\) is the next bichromatic edge along the traversal. In this case, we record the edge associated with \(x_b\) as the next unbounded edge, advance \(x\) to a point on \(\Gamma\) immediately following \(x_b\), and update \(\bar{\lambda}(x)\) by swapping \(p\) and \(q\). Otherwise, if \(x_m\) precedes \(x_b\), we advance \(x\) to a point on \(\Gamma\) immediately following \(x_m\) and update \(\bar{\lambda}(x)\) by replacing the corresponding leader. We repeat this procedure until \(\Gamma\) is entirely traversed.

We conclude by analyzing the time complexity. Computing the monochromatic unbounded edges takes \(O(n \log n)\) time. The permutations \(\bar{\pi}(x)\) and \(\bar{\lambda}(x)\) for the starting point are also computed in \(O(n \log n)\) time. During the traversal of \(\Gamma\), we compute \(2(m-1)\) intersections for each unbounded edge in \(\overline{\mathsf{CVD}}^*_{\leqslant m}(S)\). Since there are \(O(m(n-m+1))\) unbounded edges in \(\overline{\mathsf{CVD}}^*_{\leqslant m}(S)\) by Lemmas [lem:sumU] and [lem:overlay95CVDk95star], the claimed time complexity follows. ◻

Proof. Consider the overlay of the diagrams in \(\overline{\mathsf{CVD}}^*_{\leqslant k}(S_1)\) and \(\overline{\mathsf{CVD}}^*_{\leqslant k}(S_2)\). For each \(x \in \Gamma\) that avoids any bisecting curves in \(\mathcal{J}\), let \(\pi(x, S)\) be the permutation of \(S\) induced by \(\leqslant_x\), let \(\bar{\pi}(x, S)\) be the reverse of the permutation \(\pi(x, S)\), and let \(\bar{\lambda}(x, S, k)\) be the subsequence of \(\bar{\pi}(x, S)\) containing the leaders of the \(k\) farthest colors in \(K\) with respect to \(\mathrel{\overline{\succcurlyeq}}_x\). We define the permutations for the sets \(S_1\) and \(S_2\) respectively. Traversing \(\Gamma\) corresponds to iterating through the permutations in \(\overline{\Pi}(S)\), \(\overline{\Pi}(S_1)\), and \(\overline{\Pi}(S_2)\). We assume without loss of generality that we traverse \(\Gamma\) clockwise.

For a point \(x \in \Gamma\), the subsequence \(\bar{\lambda}(x, S, k)\) can be computed by merging \(\bar{\lambda}(x, S_1, k)\) and \(\bar{\lambda}(x, S_2, k)\) according to \(\leqslant_x\) and selecting the \(k\) farthest sites from \(x\). This follows from the fact that the leaders of the \(k\) farthest colors in \(S\), with respect to \(\leqslant_x\), must be among the leaders of the \(k\) farthest colors in either \(S_1\) or \(S_2\).

We compute the unbounded edges in \(\overline{\mathsf{CVD}}^*_{\leqslant k}(S)\) by traversing \(\Gamma\), as in Lemma [lem:alg95base95case]. After selecting an arbitrary starting point \(x \in \Gamma\), we compute \(\bar{\lambda}(x, S_1, k)\) and \(\bar{\lambda}(x, S_2, k)\) by identifying the unbounded faces of \(\overline{\mathsf{CVD}}^*_{j}(S_1)\) and \(\overline{\mathsf{CVD}}^*_{j}(S_2)\) containing \(x\), for all \(1 \leqslant j \leqslant k\). Then, we compute \(\bar{\lambda}(x, S, k)\) by merging \(\bar{\lambda}(x, S_1, k)\) and \(\bar{\lambda}(x, S_2, k)\) according to \(\leqslant_x\). Let \(x_e\) be the intersection of \(\Gamma\) with the next unbounded edge from the overlay of \(\overline{\mathsf{CVD}}^*_{\leqslant k}(S_1)\) and \(\overline{\mathsf{CVD}}^*_{\leqslant k}(S_2)\) that is encountered during the traversal from \(x\). For each pair of consecutive sites \(p, q\) in \(\bar{\lambda}(x, S, k)\), we compute the two intersections between \(J({p},{q})\) and \(\Gamma\). Let \(x_b\) be the first of these \(2(k-1)\) intersections we encounter along \(\Gamma\) starting from \(x\).

If \(x_b\) precedes \(x_e\) while traversing \(\Gamma\) from \(x\), then \(x_b\) corresponds to the next switch between the leaders of two colors in \(\Lambda(\overline{\Pi}(S))\). As shown in the proof of Lemma [lem:U-G], the unbounded edge associated with \(x_b\) is the next bichromatic edge along the traversal. In this case, we record the edge associated with \(x_b\) as the next unbounded edge, advance \(x\) to a point on \(\Gamma\) immediately following \(x_b\), and update \(\bar{\lambda}(x, S, k)\) by swapping \(p\) and \(q\). Otherwise, if \(x_e\) precedes \(x_b\), we advance \(x\) to a point on \(\Gamma\) immediately following \(x_e\). We then update the corresponding subsequence (either \(\bar{\lambda}(x, S_1, k)\) or \(\bar{\lambda}(x, S_2, k)\)) based on the type of edge associated with \(x_e\): if \(x_e\) is monochromatic, we replace the corresponding leader; if \(x_e\) is bichromatic, we swap the appropriate pair of sites. After this update, we recompute \(\bar{\lambda}(x, S, k)\) by merging the updated \(\bar{\lambda}(x, S_1, k)\) and \(\bar{\lambda}(x, S_2, k)\). We repeat this procedure until \(\Gamma\) is entirely traversed.

We conclude by analyzing the time complexity. For all \(1 \leqslant j \leqslant k\), scanning the unbounded faces of \(\overline{\mathsf{CVD}}^*_{j}(S_1)\) and \(\overline{\mathsf{CVD}}^*_{j}(S_2)\) to locate the starting point \(x\) takes \(O(j(n-j+1))\) time; thus computing the initial \(\bar{\lambda}(x, S_1, k)\) and \(\bar{\lambda}(x, S_2, k)\) takes \(O(k^2(n-k+1))\) time. During the traversal of \(\Gamma\), we compute \(2(k-1)\) intersections, and potentially merge \(\bar{\lambda}(x, S_1, k)\) and \(\bar{\lambda}(x, S_2, k)\) in \(O(k)\) time, for each unbounded edge in \(\overline{\mathsf{CVD}}^*_{\leqslant k}(S_1)\), \(\overline{\mathsf{CVD}}^*_{\leqslant k}(S_2)\), and \(\overline{\mathsf{CVD}}^*_{\leqslant k}(S)\). Since there are \(O(k(n-k+1))\) such unbounded edges by Lemma [lem:sumU], the claimed time complexity follows. ◻

Proof. Partition the set of colors \(K\) into sets \(K_1\) and \(K_2\), of roughly equal sizes \(|K_1| = \lfloor m/2 \rfloor\) and \(|K_2| = \lceil m/2 \rceil\). The set \(S\) is partitioned into \(S_1\) and \(S_2\), of sizes \(|S_1| = n_1\) and \(|S_2| = n_2\). Using Lemma [lem:alg95base95case] to compute the base case and Lemma [lem:alg95merge] for the merge step, the time complexity of the divide-and-conquer algorithm is given by the following recurrence.

\[T(m,n) = \begin{cases} T(\lfloor m/2 \rfloor, n_1) + T(\lceil m/2 \rceil, n_2) + O(k^2 (n-k+1)) & \text{if } k < m/2 \\ O(m^2 (n-m+1) + n \log n) & \text{otherwise} \end{cases}\]

The number of levels in the recursion tree is \(L = \log_2(m/k) + O(1)\). Let \(n_{i,j}\) denote the number of sites in the \(j\)-th subproblem at level \(i\). For any level \(0 \leqslant i \leqslant L\), it holds that \(\sum_{j=1}^{2^i} n_{i,j} = n\). For a constant \(c>0\), the merge step at level \(i\) is bounded by:

\[\sum_{j=1}^{2^i} c k^2 (n_{i,j} - k + 1) = c k^2 n - c k^2 (k-1) 2^i\]

Summing this over all levels, the total merge work across the tree is bounded by:

\[\sum_{i=0}^{L-1} \left( c k^2 n - c k^2 (k-1) 2^i \right) = c k^2 n L - c k^2 (k-1) (2^L - 1)\]

Since \(L = \Theta(\log(m/k + 1))\) and the number of leaves is \(2^L = \Theta(m/k)\), the negative term is bounded by \(\Theta(m k^2)\). Because \(k \leqslant m \leqslant n\), this term is strictly dominated by \(c k^2 n L = O(k^2 n \log m)\); thus the total merge cost is \(O(k^2 n \log m)\).

Let \(m_{L,j} < 2k\) denote the number of colors in the \(j\)-th leaf of the recursion tree. For a constant \(c'>0\), the complexity of the base cases is bounded by:

\[\sum_{j=1}^{2^L} c' (m_{L,j}^2 (n_{L,j} - m_{L,j} + 1) + n_{L,j} \log n_{L,j})\]

Because \(m_{L,j} < 2k\), we can bound \(m_{L,j}^2\) by \(O(k^2)\). Summing across all leaves yields \(O(k^2 n + n \log n)\). Adding the total merge and base case costs together results in the claimed complexity. ◻