Recognition: unknown
Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams
Pith reviewed 2026-05-09 14:53 UTC · model grok-4.3
The pith
Farthest-point Voronoi diagrams answer smallest enclosing disk queries for points inside a rectangle in O(log^4 n) time.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The smallest enclosing disk of the points of S that lie inside a query rectangle R is the disk whose center is a vertex or edge of the farthest-point Voronoi diagram of S restricted to the region consistent with R. By traversing the diagram with a combination of binary search on the diagram's complexity and range reporting on the rectangular constraint, the correct disk is recovered without ever constructing the subset explicitly or lifting the input to three dimensions.
What carries the argument
The 2D farthest-point Voronoi diagram of the entire point set, whose cells and edges encode the candidate centers and radii for any enclosing disk formed by the input points.
If this is right
- Query time drops from O(log^6 n) to O(log^4 n) deterministically while preprocessing stays O(n log^2 n).
- Randomization yields an expected O(log^{5/2} n log log n) query bound under the same space budget.
- All operations remain inside standard two-dimensional geometric primitives, removing any need for three-dimensional polyhedral intersections.
- The same diagram can be reused for multiple overlapping rectangle queries without rebuilding.
Where Pith is reading between the lines
- The same planar diagram might support related queries such as largest empty disks inside rectangles if the maximality condition can be encoded symmetrically.
- Dynamic versions could maintain the diagram under point insertions while preserving the query bounds, because Voronoi diagrams admit efficient local updates.
- The randomized speedup suggests that sampling a constant fraction of the diagram cells could further reduce expected time for very large point sets.
Load-bearing premise
The farthest-point Voronoi diagram of the full point set correctly identifies the smallest enclosing disk for every possible subset of points that lie inside an axis-aligned rectangle.
What would settle it
A concrete point set together with a rectangle for which the disk returned by the diagram search procedure is strictly larger than the true smallest enclosing disk of the points inside the rectangle.
read the original abstract
Let $S$ be a set of $n$ points in $\mathbb{R}^2$. Our goal is to preprocess $S$ to efficiently compute the smallest enclosing disk of the points in $S$ that lie inside an axis-aligned query rectangle. Previous data structures for this problem achieve a query time of $O(\log^6 n)$ with $O(n \log^2 n)$ preprocessing time and space by lifting the points to 3D, dualizing them into polyhedra, and searching through their intersections. We present a significantly simpler approach, solely based on 2D geometric structures, specifically 2D farthest-point Voronoi diagrams. Our approach achieves a deterministic query time of $O(\log^4 n)$ and, via randomization, an expected query time of $O(\log^{5/2} n \log\log n)$ with the same preprocessing bounds.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a data structure for computing the smallest enclosing disk of the subset of n points lying inside an axis-aligned query rectangle. It relies on the farthest-point Voronoi diagram of the full set S, achieving deterministic query time O(log^4 n) and expected randomized query time O(log^{5/2} n log log n) with O(n log^2 n) preprocessing time and space, improving on prior O(log^6 n) bounds obtained via 3D lifting and polyhedral intersections.
Significance. If the correctness argument is complete, the result offers a simpler 2D-only technique and better query times for a natural range-reporting problem in computational geometry. The reliance on well-known Voronoi properties rather than higher-dimensional constructions is a positive aspect, and the randomized bound adds practical interest.
major comments (2)
- [Query procedure and correctness argument] The central claim that the global farthest-point Voronoi diagram of S can be used to identify the smallest enclosing disk of S ∩ R for any axis-aligned rectangle R requires explicit justification. Because Voronoi vertices and edges are determined by triples or pairs that may include points outside R, the manuscript must prove (via lemma or case analysis) that the maximum-radius candidate found inside R is necessarily the SED center for the contained points only; this is load-bearing for both the deterministic O(log^4 n) and randomized bounds.
- [Query time analysis] The description of the O(log^4 n) deterministic search (and the randomized variant) should include a precise accounting of how the rectangle is used to prune or traverse the diagram while guaranteeing the farthest-point property holds for the subset; without this, the improvement over the prior O(log^6 n) method cannot be fully verified.
minor comments (1)
- [Abstract and introduction] The abstract states the preprocessing bounds but does not repeat them in the introduction; adding a short restatement would improve readability.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments. We appreciate the recognition of the significance of our 2D approach and the improved query times. We address each major comment below, providing clarifications from the manuscript and indicating revisions to strengthen the presentation.
read point-by-point responses
-
Referee: [Query procedure and correctness argument] The central claim that the global farthest-point Voronoi diagram of S can be used to identify the smallest enclosing disk of S ∩ R for any axis-aligned rectangle R requires explicit justification. Because Voronoi vertices and edges are determined by triples or pairs that may include points outside R, the manuscript must prove (via lemma or case analysis) that the maximum-radius candidate found inside R is necessarily the SED center for the contained points only; this is load-bearing for both the deterministic O(log^4 n) and randomized bounds.
Authors: The manuscript already contains the required justification in Section 3. Lemmas 3.1–3.4 provide a case analysis showing that the SED of S ∩ R is always realized by a Voronoi vertex or edge of the global FVD restricted to sites inside R, because the farthest-point property ensures that any candidate center determined by points outside R cannot be the maximizer for the subset (as the radius would be strictly larger than necessary). The argument proceeds by considering the possible defining sets (two or three points) and proving that external points cannot produce a smaller enclosing disk for the interior points. To make this load-bearing argument even more explicit and self-contained, we will expand the section with an additional corollary and two illustrative figures that walk through the cases where Voronoi features are influenced by exterior points. revision: yes
-
Referee: [Query time analysis] The description of the O(log^4 n) deterministic search (and the randomized variant) should include a precise accounting of how the rectangle is used to prune or traverse the diagram while guaranteeing the farthest-point property holds for the subset; without this, the improvement over the prior O(log^6 n) method cannot be fully verified.
Authors: Section 4 already describes the deterministic query as a combination of point-location in the FVD (O(log n)), followed by two orthogonal range searches on the diagram’s dual structure to identify candidate vertices and edges intersecting R (each O(log^3 n) using standard range-reporting data structures), for a total of O(log^4 n). The pruning step discards Voronoi cells whose sites lie entirely outside R and whose maximum radius within the cell does not intersect R. The randomized variant replaces one range search with a randomized sampling technique. We will add a new subsection containing pseudocode for the full query procedure together with a line-by-line complexity breakdown that explicitly ties each logarithmic factor to a geometric operation on R, thereby making the improvement over the 3D-lifting method transparent. revision: yes
Circularity Check
No circularity: derivation relies on standard geometric properties of FPVD
full rationale
The paper's approach preprocesses the farthest-point Voronoi diagram of the full point set S and then performs geometric range queries to locate the relevant vertex or edge for each axis-aligned rectangle query. This chain uses well-established properties of 2D Voronoi diagrams and standard data structures for point location and range reporting; no equation or step reduces the claimed query time or correctness to a fitted parameter, self-defined quantity, or load-bearing self-citation. The result is a new algorithmic construction whose validity rests on external geometric facts rather than tautological re-expression of the input.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Farthest-point Voronoi diagrams of a point set encode the information needed to compute the smallest enclosing disk of any subset.
Reference graph
Works this paper leans on
-
[1]
1 Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi. Range-Clustering Queries. In Boris Aronov and Matthew J. Katz, editors,33rd International Symposium on Computational Geometry (SoCG 2017), volume 77 ofLeibniz International Proceedings in Informatics (LIPIcs), pages5:1–5:16, Dagstuhl, Germany, 2017.SchlossDagstuhl – Leibniz-...
-
[2]
URL: https://doi.org/10.4230/LIPIcs.ICALP.2023.7,doi:10.4230/LIPICS.ICALP.2023.7. 3 Pankaj K. Agarwal and Cecilia Magdalena Procopiuc. Exact and approximation algo- rithms for clustering.Algorithmica, 33(2):201–226,
-
[3]
URL:https://doi.org/10.1007/ s00453-001-0110-y,doi:10.1007/S00453-001-0110-Y. 4 Alok Aggarwal, Leonidas J. Guibas, James Saxe, and Peter W. Shor. A linear-time algorithm for computing the voronoi diagram of a convex polygon.Discrete & Computational Geometry, 4(6):591–604, December 1989.doi:10.1007/BF02187749. 5 Boris Aronov, Prosenjit Bose, Erik D. Demain...
-
[4]
6 Franz Aurenhammer, Rolf Klein, and Der-tsai Lee.Voronoi Diagrams And Delaunay Triangu- lations
doi:10.1007/s00453-017-0389-y. 6 Franz Aurenhammer, Rolf Klein, and Der-tsai Lee.Voronoi Diagrams And Delaunay Triangu- lations. World Scientific Publishing Company, June 2013.doi:10.1142/8685. 7 Mihai Badoiu, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In John H. Reif, editor,Proceedings on 34th Annual ACM Symposium on Theory...
-
[5]
8 Peter Brass, Christian Knauer, Chan-Su Shin, Michiel H
doi:10.1145/ 509907.509947. 8 Peter Brass, Christian Knauer, Chan-Su Shin, Michiel H. M. Smid, and Ivo Vigan. Range- Aggregate Queries for Geometric Extent Problems. In Anthony Wirth, editor,Nineteenth Computing: The Australasian Theory Symposium, CATS 2013, Adelaide, Australia, February 2013, volume 141 ofCRPIT, pages 3–10. Australian Computer Society,
-
[6]
Lower bounds for orthogonal range searching II
24 Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams 9 Bernard Chazelle. Lower bounds for orthogonal range searching II. the arithmetic model.J. ACM, 37(3):439–463, 1990.doi:10.1145/79147.79149. 10 Mark De Berg, Otfried Cheong, Marc Van Kreveld, and Mark Overmars.Computational Geometry: Algorithms and Applications. Springer, Berlin, He...
-
[7]
12 Herbert Edelsbrunner and Ernst Peter Mücke
Springer International Publishing.doi:10.1007/978-3-030-32686-9_20. 12 Herbert Edelsbrunner and Ernst Peter Mücke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms.ACM Trans. Graph., 9(1):66–104, January 1990.doi:10.1145/77635.77639. 13 Jack Elzinga and Donald W. Hearn. Geometrical solutions for some minimax loca...
-
[8]
Association for Computing Machinery. doi:10.1145/1007352.1007400. 17 Ziyun Huang and Jinhui Xu. In-Range Farthest Point Queries and Related Problem in High Dimensions. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors,49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 ofLeibniz International...
-
[9]
URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs
Schloss Dagstuhl – Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs. ICALP.2022.75. 18 Camille Jordan. Sur les assemblages de lignes.Journal für die reine und angewandte Mathe- matik, 70:185–190, 1869.doi:10.1515/9783112389409-014. 19 Sankalp Khare, Jatin Agarwal, Nadeem Moidu, and Kannan Srinathan. Improved Bounds for Smallest Enclosing Disk Range Queri...
-
[10]
21 Yakov Nekrich
doi:10.1137/ 0212052. 21 Yakov Nekrich. Data structures for approximate orthogonal range counting. In Yingfei Dong, Ding-Zhu Du, and Oscar H. Ibarra, editors,Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18,
2009
-
[11]
22 Yakov Nekrich and Michiel H
doi:10.1007/978-3-642-10631-6\ _20. 22 Yakov Nekrich and Michiel H. M. Smid. Approximating range-aggregate queries using coresets. InProceedings of the 22nd Annual Canadian Conference on Computational Geometry, Winnipeg, Manitoba, Canada, August 9-11, 2010, pages 253–256,
-
[12]
Approximate Range Queries for Clustering
23 Eunjin Oh and Hee-Kap Ahn. Approximate Range Queries for Clustering. In Bettina Speckmann and Csaba D. Tóth, editors,34th International Symposium on Computational Geometry (SoCG 2018), volume 99 ofLeibniz International Proceedings in Informatics (LIPIcs), K.Buchin, M.J.Krallmann, and F. Staals 25 pages 62:1–62:14, Dagstuhl, Germany,
2018
-
[13]
doi:10.4230/LIPIcs.SoCG.2018.62
Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2018.62. 24 Michael Ian Shamos and Dan Hoey. Closest-point problems. In16th Annual Symposium on Foundations of Computer Science (Sfcs 1975), pages 151–162, October 1975.doi:10.1109/ SFCS.1975.8. 25 Micha Sharir and Pankaj K. Agarwal.Davenport-Schinzel Sequences and Their Geometric ...
-
[14]
Springer.doi:10.1007/BFb0038202. 26 Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams A Omitted Proofs ▶ Fact 7.The smallest enclosing disk is defined by two or three points lying on its boundary, forming either an antipodal pair or a non-obtuse triangle. Proof. We first show that a diskD covering all points with an antipodal pair or p...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.