Pith. sign in

REVIEW 12 references

Abstract Color Voronoi Diagrams and Circular Sequences of Color Permutations

T0 review · reviewed 2026-07-07 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Tight bound 4k(n−k)−2n proven for color Voronoi diagrams

desk verdict Tight complexity bound for order-k abstract color Voronoi diagrams — resolves the polygon case and removes a key assumption from prior work. read the letter →

arxiv 2607.05383 v1 pith:PGU66PEX submitted 2026-07-06 cs.CG

Sang Won Bae , Nicolau Oliver , Evanthia Papadopoulou This is my paper · ORCID
classification cs.CG
keywords abstractcolorvoronoidiagramssimpleboundcircularcombinatorial
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that the order-k abstract color Voronoi diagram — a partition of the plane by the k nearest colors among n sites carrying m ≤ n colors — has at most 4k(n−k)−2n vertices, and that this bound is tight. The result holds simultaneously for every concrete Voronoi instance that falls under the abstract Voronoi diagram umbrella, including points, line segments, and convex objects under any Lp metric, as well as for both the minimal variant (k nearest colors) and the maximal variant (k farthest colors). The central mechanism is a two-stage reduction: first, a colorful extension of the Clarkson–Shor random-sampling technique expresses the vertex count of the order-k diagram in terms of the diagram's unbounded edges (Lemma 11); second, tight bounds on those unbounded-edge counts are derived from a purely combinatorial analysis of circular sequences of permutations of colored elements (Theorem 17, Lemma 12). The bound directly resolves the previously open problem of bounding the complexity of the order-k Voronoi diagram of disjoint simple polygons.

What carries the argument

The colorful Clarkson–Shor framework (adapting the classical random-sampling technique to colored configurations), circular sequences of permutations of colored elements (a colored variant of allowable sequences), and the correspondence between switches in these sequences and unbounded edges of the diagrams.

What would settle it

A concrete instance of an admissible bisecting curve system with n colored sites where the order-k color Voronoi diagram has more than 4k(n−k)−2n vertices, or a circular sequence of colored permutations satisfying (P1)–(P2) where G_k falls outside [k(k+1), k(2n−k−1)].

Watch

Extended reading notes

Core claim

The exact maximum number of vertices in the order-k abstract color Voronoi diagram, both minimal and maximal, is 4k(n−k)−2n, and this is tight. The proof reduces vertex counting to unbounded-edge counting via the colorful Clarkson–Shor framework, then bounds the unbounded edges by analyzing switches in circular sequences of permutations of colored elements — a colored variant of allowable sequences. The lower bound k(k+1) and upper bound k(2n−k−1) on the cumulative unbounded-edge quantities G_k are both proven tight by explicit constructions of circular sequences. For disjoint simple polygons of total complexity n, the order-k polygon Voronoi diagram has complexity O(min{k(n−k), (m−k)²n}), a

Load-bearing premise

The proof requires that the underlying bisecting curves satisfy four admissibility axioms, the most restrictive being that every nearest Voronoi region is non-empty and pathwise connected for every subset of sites. This holds for points, disjoint segments, and convex objects under Lp metrics, but excludes crossing segments and non-convex objects. A general-position assumption (at most three related bisectors meet at a point) is also load-bearing for the vertex characteriza

Editorial extensions

If this is right

  • The complexity of the order-k Voronoi diagram of disjoint simple polygons — previously open for all orders except the farthest — is now bounded by O(min{k(n−k), (m−k)²n}).
  • The abstract farthest color Voronoi diagram and the abstract Hausdorff Voronoi diagram both have worst-case complexity O(m(n−m+1)), applicable to all concrete cases under the AVD umbrella, improving the previous O(mn) bound when m is close to n.
  • An iterative algorithm computes both minimal and maximal order-k color Voronoi diagrams in O(k²n log n) time, and a reverse-order algorithm computes ordinary abstract Voronoi diagrams from order n−1 down to k in O((n−k)²n log n) time — the first such algorithm known.
  • The combinatorial analysis of colored circular sequences (Theorem 17) is stated to be of independent interest and may find applications in analyzing other geometric structures defined by colored objects.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The colored allowable-sequence framework could potentially extend to higher-dimensional or non-Euclidean settings where bisector systems still satisfy admissibility axioms, offering a route to bounding higher-order color diagrams in dimensions beyond the plane.
  • The gap between the general bound O(k(n−k)) and the sharper O((m−k)²n) for large k suggests that the true complexity of the order-k polygon Voronoi diagram at intermediate k (e.g., k = m/2) may be strictly below both bounds — the authors themselves flag this as an open question.
  • If the admissibility axioms could be relaxed to accommodate crossing segments or non-convex objects, the same proof machinery would extend the tight bound to those site classes, but the pathwise-connectedness axiom (A1) is the structural obstacle.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 0 minor

Summary. This paper introduces higher-order abstract color Voronoi diagrams (CVD_k and CVD̄_k) under the abstract Voronoi diagram (AVD) framework, proving that the number of vertices in the order-k diagram is at most 4k(n−k)−2n, and that this bound is tight. The result applies to all concrete Voronoi diagram instances satisfying the AVD admissibility axioms, including the previously open order-k polygon Voronoi diagram. The proof combines two ingredients: (1) a colorful Clarkson–Shor framework (Lemma 11) that reduces vertex counting to unbounded-edge quantities U_k and Ũ_k, and (2) a purely combinatorial analysis of circular sequences of colored permutations (Theorem 17, proved via Lemmas 18–25) that provides tight bounds on those quantities (Lemma 12). The paper also gives an iterative construction algorithm running in O(k²n log n) time and a sharper O(min{k(n−k), (m−k)²n}) bound for polygon sites.

Significance. The central result is significant: it resolves the combinatorial complexity of order-k Voronoi diagrams of simple polygons, which had been open, and it does so within the unifying AVD framework, simultaneously covering segments, disks, convex objects under Lp metrics, and more. The proof structure is clean and well-organized. The combinatorial analysis of colored circular sequences (Section 5) is an independently interesting contribution with explicit tight constructions (Lemma 25). The algorithmic results, including the reverse-order computation of abstract VD_k (Corollary 30), are a useful byproduct. The paper provides falsifiable, tight bounds with verifiable constructions.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the positive assessment. The referee report recommends minor revision but does not list specific major comments under the MAJOR COMMENTS heading. We have reviewed the manuscript against the referee's summary and significance assessment and identified several points where clarifications or minor corrections are warranted. We address these below.

read point-by-point responses

  1. Referee: The referee report's MAJOR COMMENTS section is empty, so we respond to the points raised in the summary and significance assessment.

    Authors: We note that the referee's summary and significance assessment are accurate and faithfully represent the contributions of the paper. We have carefully re-examined the manuscript in light of the referee's description and identified a few minor issues that we will address in revision. (1) In the abstract and introduction, the phrase 'tight bounds' is used; we will ensure it is consistently qualified as 'tight up to constant factors' where asymptotic notation is used (e.g., in Theorem 14 and Corollary 15), while the exact bound 4k(n-k)-2n in Theorem 13 is indeed tight as stated. (2) In the proof of Lemma 11, there is a typo: 'Ppart (2)' should read 'Part (2)'. (3) In Section 5.1.2, the derivation of the upper bound on G_k involves summing Lemma 24 over all elements; we will add one sentence clarifying that the sum over initial leaders t in lambda_0 yields the first sum (over a=1 to m of min{2(a-1),2k}) and the remaining n-m elements each contribute 2k, for a total of k(k-1)+2k(n-k)=k(2n-k-1). (4) In Lemma 26, the time complexity is stated as O(m^2(n-m+1)+n log n); we will add a brief justification that the O(n log n) term accounts for computing the initial permutation and the monochromatic unbounded edges. (5) We will add a remark in Section 7 noting that the bound O(min{k(n-k),(m-k)^2 n}) for polygon sites may not be tight for all k, as already acknowledged in the concluding remarks. None of these changes affect the correctness of the results. revision: partial

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity found; the central bound is derived from independently proved lemmas

full rationale

The paper's central result (Theorem 13: vertex count ≤ 4k(n−k)−2n) rests on two pillars: Lemma 11, which adapts the colorful Clarkson–Shor framework from [11] (same authors) to express vertex counts in terms of unbounded-edge quantities U_k and Ũ_k, and Lemma 12, which bounds these quantities. I checked both for circularity. For Lemma 11, the paper does not merely cite [11] for the result—it explicitly constructs the CS-structures (configurations V and U, conflict relations χ, χ̄, χ′, χ̄′), verifies they are CS-structures, and derives the linear system V_k + U_k = k(2n−k−1) and V̄_k − Ũ_k = −k(k+1) from first principles using the standard Clarkson–Shor lower/upper bound lemmas. The self-citation to [11] is for a technique/framework, not for the target result. For Lemma 12, the bounds k(k+1) ≤ Ũ_k ≤ k(2n−k−1) are proved via Theorem 17, which is established through a purely combinatorial argument on colored circular sequences (Lemmas 18–24) with no dependency on [11]. The lower bound charges switches to colors (Lemmas 18–21) and the upper bound charges switches to elements (Lemmas 22–24); the key algebraic identity in Lemma 24 (min{j₁−1,k} + max{k−j₁+1,0} = k) is verified. Tightness is shown by explicit constructions in Lemma 25 (sequences Σ_{n,m} and Σ′_{n,m}), which are verifiable and independent. The arithmetic in Theorem 13's proof checks out: substituting U_k ≥ k(k+1) into the CVD_k formula and Ũ_k ≤ k(2n−k−1) into the CVD̄_k formula both yield exactly 4k(n−k)−2n. The self-citation to [11] is load-bearing for the framework but not circular: [11] provides a technique, the paper re-derives the equations in a more general setting, and the novel contribution (Lemma 12/Theorem 17) is independently proved. Score 1 reflects the technique-level self-citation without any reduction of the central claim to its own inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are introduced; all bounds are exact functions of n, m, k. No new physical or mathematical entities are postulated. The axioms are standard in the AVD literature or cited from prior work. The 'closed curve at infinity' Γ (Section 2) is a standard construction, not a new entity.

assumptions (5)
  • domain assumption Admissibility axioms (A1)–(A4) for the bisecting curve system J: (A1) each VR(p,S') is non-empty and pathwise connected; (A2) plane is covered by closures of VR(p,S'); (A3) each bisector is unbounded and completes to a Jordan curve through the north pole under stereographic projection; (A4) any two,
    Section 2. These are the standard AVD axioms from Klein [28]. They define the class of problems to which the results apply. Verification for concrete instances requires constant-size examples [13].
  • domain assumption General position: only three related bisecting curves intersect at the same point.
    Section 2. Used throughout for degree-3 vertex counting (Lemma 10) and vertex characterization (Lemmas 8–9). The paper notes (A4) can be relaxed per [29] but retains it for simplicity.
  • standard math The colorful Clarkson–Shor framework [11, Lemma 2 and 3] applies to color-augmented CS-structures derived from admissible bisector systems.
    Invoked in the proof of Lemma 11 (Section 4). This is a random sampling technique from [11] (SoCG 2025), which itself extends the classical Clarkson–Shor technique [22].
  • standard math Any circular sequence Π satisfying (P1) and (P2) can be realized by an admissible system of bisecting curves [13, Lemma 10].
    Section 5, after Lemma 16. Used to transfer the purely combinatorial bounds of Theorem 17 back to the geometric setting, establishing tightness of Lemma 12.
  • standard math The farthest polygon Voronoi diagram has linear complexity O(n) [21].
    Section 4, before Corollary 15. Used as the base case T₀(x)=x in Theorem 14 to derive the improved bound O((m−k)²n) for large k.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Abstract Color Voronoi Diagrams and Circular Sequences of Color Permutations." pith.science (2026). https://pith.science/paper/PGU66PEX

@misc{pith2026260705383,
  author       = {Pith},
  title        = {Pith review of: Abstract Color Voronoi Diagrams and Circular Sequences of Color Permutations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PGU66PEX}},
  note         = {Machine review of arXiv:2607.05383}
}
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [11]

    38 Evanthia Papadopoulou

    doi: 10.1109/43.920683. 38 Evanthia Papadopoulou. The Hausdorff Voronoi diagram of point clusters in the plane. Algorithmica, 40(2):63–82, 2004.doi:10.1007/s00453-004-1095-0. 39 Evanthia Papadopoulou. Net-aware critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams.IEEE T. Comput. Aid. D., 30(5):704–716,

    work page doi:10.1109/43.920683 2004

  2. [1]

    Agarwal, Mark de Berg, Jiří Matoušek, and Otfried Schwarzkopf

    2 Pankaj K. Agarwal, Mark de Berg, Jiří Matoušek, and Otfried Schwarzkopf. Constructing levels in arrangements and higher order Voronoi diagrams.SIAM J. Comput., 27(3):654–667, 1998.doi:10.1137/S0097539795281840. 3 Alok Aggarwal, Leonidas J. Guibas, James B. Saxe, and Peter W. Shor. A linear-time algorithm for computing the Voronoi diagram of a convex pol...

    work page doi:10.1137/s0097539795281840 1998

  3. [2]

    2014.04.005

    doi:10.1016/j.comgeo. 2014.04.005. 11 Sang Won Bae, Nicolau Oliver, and Evanthia Papadopoulou. Higher-order color Voronoi diagrams and the colorful Clarkson–Shor framework. InProc. 41st International Symposium on Computational Geometry (SoCG 2025), volume 332 ofLIPIcs, pages 12:1–10:19,

    work page doi:10.1016/j.comgeo 2014

  4. [3]

    On the Size of Chromatic Delaunay Mosaics.Discrete & Computational Geometry, 75(1):24–47, January 2026.doi:10.1007/s00454-025-00778-7

    12 Ranita Biswas, Sebastiano Cultrera di Montesano, Ondřej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. On the Size of Chromatic Delaunay Mosaics.Discrete & Computational Geometry, 75(1):24–47, January 2026.doi:10.1007/s00454-025-00778-7. 13 Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou, and Maksym Zavers...

    work page doi:10.1007/s00454-025-00778-7 2026

  5. [4]

    17 Timothy M

    doi: 10.1007/s00454-004-1152-0. 17 Timothy M. Chan. Random sampling, halfspace range reporting, and construction of (≤k)-levels in three dimensions.SIAM J. Comput., 30(2):561–575,

    work page doi:10.1007/s00454-004-1152-0

  6. [5]

    Kothari, Yang P

    doi:10.1137/ S0097539798349188. 18 Timothy M. Chan, Pingan Cheng, and Da Wei Zheng. An optimal algorithm for higher-order Voronoi diagrams in the plane: The usefulness of nondeterminism. In David P. Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, V A, USA, January 7-10, 2024, pages 4451–4463. SIAM...

    work page doi:10.1137/1 2024

  7. [6]

    20 Lisi Chen, Shuo Shang, Chengcheng Yang, and Jing Li

    doi:10.1007/ s00454-016-9784-4. 20 Lisi Chen, Shuo Shang, Chengcheng Yang, and Jing Li. Spatial keyword search: a survey. GeoInformatica, 24(1):85–106, 2020.doi:10.1007/s10707-019-00373-y. 21 Otfried Cheong, Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, Sylvain Lazard, Mira Lee, and Hyeon-Suk Na. Farthest-polygon Voronoi diagrams.Comput....

    work page doi:10.1007/s10707-019-00373-y 2020

  8. [7]

    24 Jacob E

    doi:10.1007/BF02187733. 24 Jacob E. Goodman and Richard Pollack. On the number ofk-subsets of a set ofn points in the plane.J. Combinat. Theory, Series A, 36(1):101–104,

    work page doi:10.1007/bf02187733

Show all 12 references
  1. [8]

    25 Jacob E

    doi:10.1016/0097-3165(84) 90081-5. 25 Jacob E. Goodman and Richard Pollack. Allowable sequences and order types in discrete and computational geometry. InNew Trends in Discrete and Computational Geometry, pages 103–

    doi

  2. [9]

    Springer-Verlag, Berlin, Heidelberg, New York, 1993.doi:10.1007/978-3-642-58043-7_

    1993 doi

  3. [10]

    28 Rolf Klein.Concrete and Abstract Voronoi Diagrams, volume 400 ofLecture Notes in Computer Science

    doi:10.1007/ BF02189323. 28 Rolf Klein.Concrete and Abstract Voronoi Diagrams, volume 400 ofLecture Notes in Computer Science. Springer-Verlag, Berlin, Heidelberg, New York, 1989.doi:10.1007/3-540-52055-4. 29 Rolf Klein, Elmar Langetepe, and Zahra Nilforoushan. Abstract Vorono...

    1989 doi

  4. [12]

    41 Evanthia Papadopoulou and Maksym Zavershynskyi

    doi:10.1142/S0218195913600121. 41 Evanthia Papadopoulou and Maksym Zavershynskyi. The higher-order Voronoi diagram of line segments.Algorithmica, 74(1):415–439, 2016.doi:10.1007/s00453-014-9950-0. 42 Edgar A. Ramos. On range reporting, ray shooting, andk-level construction. In...

    2016 doi

Pith tools

Reviewed July 7, 2026 · model on record in the stance chip above.