REVIEW 3 major objections 4 minor 19 references
Extraction Theorems With Small Extraction Numbers
T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Extraction number 2 for intervals, 4 for segments and octants, with tight bounds all around.
desk verdict The extraction-number results look correct in substance, but the proof of Lemma 5 (type-4 rays) is a real gap as written and needs a proper argument before this is publishable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing identity is Proposition 1, which equates an extraction number with a hypergraph coloring number: a polynomial-time proper κ-coloring of the hypergraph induced by a class of objects yields an extraction theorem with extraction number κ. For intervals, the coloring is constructed greedily from 'key intervals' that form a chain of pairwise consecutive overlaps. For axis-parallel segments, the horizontal and vertical subfamilies are each 2-colored, giving four colors total. For rays, 'dominating rays' (the extremal starting point in each overlapping set) anchor a 2-coloring for two orientations, extended to 3 colors for three orientations. For four orientations, each ray is treated as a finite segment with extremal points on the ray as endpoints, reusing the segment coloring; this truncation step is the weakest link in the chain. For octants, each octant is projected onto the plane x + y + z = c, where the projections are equilateral, same-oriented pseudo-disks, and the known 4-colorability of pseudo-disk hypergraphs supplies the coloring.
What would settle it
Check the hyperedge at a point lying far beyond the chosen truncation endpoints of two same-orientation type-4 rays; if the two rays receive the same color and no other ray covers that point, the Lemma 5 coloring is not proper for the ray hypergraph, so the extraction number 4 claim for type-4 rays collapses.
Extended reading notes
Core claim
The central claim is that for four natural classes of geometric objects the extraction number is small and exactly determined. For intervals it is 2; for axis-parallel segments it is 4; for axis-parallel rays admitting i distinct orientations (i = 2, 3, 4) it is i; and for octants containing (+∞, +∞, +∞) it is 4. The upper bounds come from a uniform lemma: if the hypergraph induced by a class admits a proper κ-coloring computable in polynomial time, then the extraction theorem holds with extraction number κ. The paper supplies such colorings—a greedy 2-coloring for intervals, a 4-coloring for segments that 2-colors horizontal and vertical families independently, 2- and 3-colorings for two- and three-orientation ray sets with dominating rays, a 4-coloring for four-orientation rays by treating each ray as a truncated segment, and a 4-coloring for octants by projecting them onto a plane where their cross-sections form pseudo-disks. Tightness is shown by explicit configurations: two overlapping intervals; an axis-parallel segment arrangement with small independence number; a layered three-orientation ray arrangement; the same arrangement extended to rays for the four-orientation case; and four pairwise-intersecting octants. All colorings, and hence the extraction covers, are computable in polynomial time.
Load-bearing premise
For four-type rays, the proof treats each ray as a finite segment via extremal points on the rays but never checks that points arbitrarily far along the open direction of a ray are properly colored after truncation.
Editorial extensions
If this is right
- For every weighted instance of these classes with each point contained in at least two objects, one can discard objects of weight at least W(O)/2, W(O)/4, W(O)/i, or W(O)/4 respectively and still cover all points.
- The polynomial-time colorings yield polynomial-time algorithms constructing such covers for all four classes.
- The lower-bound examples certify that these fractions cannot be improved for any of the classes.
- Because extraction numbers equal the hypergraph coloring numbers in this framework, any improved proper coloring for a class would immediately improve its extraction number.
Reading between the lines
- A rigorous account of Lemma 5's truncation step—specifying how far the 'extremal points' must extend and proving the coloring stays proper for unbounded hyperedges—is needed before the type-4 ray result is fully established. (Our inference, not stated in the paper.)
- The projection trick for octants suggests analogous extraction bounds for any 3D object class whose intersections with a suitable plane are pseudo-disks, such as translates of a fixed convex body.
- The framework should transfer to other weighted covering objectives, e.g., prize-collecting or budgeted covering, where the discarded-weight guarantee becomes a lower bound on saved cost.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the extraction number, introduced through the Extraction Theorem for disks, in which a class of geometric objects has extraction number α if, for any weighted family and any point set each contained in at least two objects, one can always remove objects of weight at least W/α while still covering all points. The authors link extraction numbers to proper colorings of geometric hypergraphs (Proposition 1) and then claim tight extraction numbers for intervals (2), axis-parallel segments (4), axis-parallel rays of type i for i∈{2,3,4} (i), and octants in 3D (4). The proofs proceed by constructing low-chromatic proper colorings of the corresponding hypergraphs and by giving lower-bound constructions.
Significance. If the main results hold, the paper establishes the smallest possible extraction numbers for several basic geometric families, which is a clean and useful contribution. Proposition 1 is a neat framework connecting extraction theorems to hypergraph coloring, and the interval and axis-parallel-segment sections are largely sound. The lower-bound constructions use known results appropriately, especially the independence-number bound of Caoduro et al. for the segment construction. However, the upper-bound proofs for type-4 rays and for octants contain substantial gaps, so the central claims are not established as written. The paper does not ship code or machine-checked proofs; its value rests on the correctness of the coloring arguments.
major comments (3)
- [Section 3.3, Lemma 5] The proof of Lemma 5 is a single sentence: 'each ray can be treated as a segment with extremal points on the rays acting as endpoints of the segment.' No extremal points are defined, and the reduction is not valid as stated. Truncating a ray at a finite point removes exactly the hyperedges corresponding to points far in the direction in which the ray opens; for any point beyond the truncation, the ray still contains it in the original hypergraph but the truncated segment does not. Thus the segment hypergraph is a strict sub-hypergraph of the ray hypergraph, and a proper 4-coloring of the sub-hypergraph need not be proper for the original ray hypergraph. Since Theorem 4's upper bound for type-4 rays rests on Lemma 5, this is a load-bearing gap. The gap is repairable: applying Lemma 3 separately to the two horizontal orientations and to the two vertical orientations, with disjoint color pairs, would give a proper 4-coloring directly. The text should be rewritten to give that argument or another rigorous proof.
- [Section 3.4, Lemma 6 and Theorem 5] The octant upper-bound proof is not valid as written. Observation 2 asserts that the projected triangles form a pseudo-disk family because they are equilateral and identically oriented; this requires a proof or citation, since homothety-to-pseudo-disk is not immediate from the text. More importantly, the final step of the properness proof is a non sequitur: from the fact that the projections of O_i and O_j intersect, the paper concludes 'so the two projected triangles are colored by distinct colors.' A proper coloring of the pseudo-disk hypergraph H(T') only guarantees that every cell is non-monochromatic; it does not guarantee that any two intersecting pseudo-disks receive distinct colors. A third triangle can cover the intersection of two others, allowing the two to share a color while the cell still contains a different color. The proof also never defines a projection of an arbitrary point p ∈ R^3 to the plane x+y+z = c_max that preserves membership in the octants, so it is unclear how properness of H(T') transfers to H(O). Since Lemma 6 is the entire basis for the octant extraction number 4, this gap must be fixed before the claim is established.
- [Section 3.4, Theorem 5 lower bound] The lower-bound construction for octants is too terse. The sentence 'there exists a region (shown by 6 shaded regions) which is the intersection of exactly two pairwise intersecting triangles' is ambiguous and does not by itself imply that six points, one in each pairwise intersection and in no other octant, can be placed. To make the argument rigorous, the paper should state explicitly that for each of the six pairs of octants there is a point contained in exactly those two octants; then any cover must be a vertex cover of K_4 and therefore needs at least three octants. As written, the lower bound for octants is not fully demonstrated.
minor comments (4)
- [Section 3.2, proof of Theorem 3] The name 'Coaduro et al.' in the lower-bound proof should be 'Caoduro et al.' to match reference [4].
- [Section 3.4, Observation 2] Even if the pseudo-disk claim is true, it should be stated with a precise definition of pseudo-disks and a citation to the standard fact that homothetic copies of a convex body form a pseudo-disk family.
- [Section 3.3, Lemma 4] The WLOG statement 'we assume that the rays in R1, R2 are parallel to the x-axis' should justify that every type-3 configuration, after reflection or rotation, has two orientations on one axis and one on the other.
- [Section 3.3, Lemma 3 and Lemma 4] The term 'dominating ray' is used for maximal overlapping groups, but the groups are not defined precisely. Please specify that these are maximal sets of pairwise overlapping rays of the same orientation, or otherwise clarify the decomposition.
Circularity Check
No significant circularity: the extraction bounds are derived from independent proper-coloring results and external lower-bound theorems, not from the paper's own outputs.
full rationale
The paper's derivation chain is not circular. The central framework (Proposition 1) is proved directly: given a proper k-coloring of the induced hypergraph, removing the heaviest color class leaves a cover because every point lies in at least two objects and hence in a non-monochromatic hyperedge. This proof is self-contained and does not depend on the extraction theorem for disks or any prior bound that is being re-proved. The new upper bounds come from original coloring lemmas: Lemma 1 gives a direct 2-coloring for interval hypergraphs, Lemma 2 combines these with disjoint color pairs for horizontal and vertical segments, Lemmas 3 and 4 give 2- and 3-colorings for type-2 and type-3 rays, and Lemma 6 uses Keszegh's externally published pseudo-disk coloring [14] after projecting octants. The lower bounds are also independent: the segment and ray lower bounds use the independence-number theorem of Caoduro et al. [4] for a specific explicit construction, and the octant lower bound is a direct construction. The authors do cite their own related work, e.g., [3] for the extraction theorem framework and linear-union-complexity classes, but those citations only motivate the problem; none of the claimed new results reduces to them. The one substantive weakness is Lemma 5: the claim that type-4 ray hypergraphs can be handled by 'treating each ray as a segment with extremal points on the rays acting as endpoints' is not a circular step, but rather an unproved truncation argument. A finite truncation omits far-away unbounded hyperedges, so the stated proof does not establish the claimed 4-coloring of the original ray hypergraph. This is a correctness gap, not a case of the result being equal to its inputs by construction, and it does not change the circularity assessment. Overall, no fitted parameter is renamed as a prediction and no 'uniqueness' or prior result by the same authors is used to force the conclusions.
Assumptions & free parameters
assumptions (4)
- standard math Pseudo-disk hypergraphs admit a polynomial-time proper 4-coloring (cited from [14]).
- domain assumption Same-oriented homothetic equilateral triangles form pseudo-disks.
- ad hoc to paper Rays can be replaced by finite segments for the purpose of the 4-coloring in Lemma 5.
- domain assumption The independence-number bound m/4 + c*sqrt(m) for the k-box segment arrangement from [4].
Cite this review
Pith. "Pith review of Extraction Theorems With Small Extraction Numbers." pith.science (2026). https://pith.science/paper/EZXMIZWS
@misc{pith2026241118655,
author = {Pith},
title = {Pith review of: Extraction Theorems With Small Extraction Numbers},
year = {2026},
howpublished = {\url{https://pith.science/paper/EZXMIZWS}},
note = {Machine review of arXiv:2411.18655}
}
read the original abstract
In this work, we develop Extraction Theorems for classes of geometric objects with small extraction numbers. These classes include intervals, axis-parallel segments, axis-parallel rays, and octants. We investigate these classes of objects and prove small bounds on the extraction numbers. The tightness of these bounds is demonstrated by examples with matching lower bounds.
Figures
Reference graph
Works this paper leans on
-
[1]
Set k-cover algorithms for energy efficient monitoring in wireless sensor networks
Zoë Abrams, Ashish Goel, and Serge Plotkin. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. InProceedings of the 3rd international symposium on Information processing in sensor networks, pages 424–432. ACM, 2004. 1
work page 2004
-
[2]
Capacitated covering problems in geometric spaces.Discret
SayanBandyapadhyay, SantanuBhowmick, TanmayInamdar, andKasturiR.Varadarajan. Capacitated covering problems in geometric spaces.Discret. Comput. Geom., 63(4):768–798, 2020. 1
work page 2020
-
[3]
Sayan Bandyapadhyay, Anil Maheshwari, Sasanka Roy, Michiel Smid, and Kasturi R. Varadarajan. Geometric covering via extraction theorem. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 ofLIPIcs, pages 7:1–7:20. Schloss Dagstuhl - Leibniz-Z...
work page 2024
-
[4]
Marco Caoduro, Jana Cslovjecsek, Michal Pilipczuk, and Karol Węgrzycki. On the independence num- ber of intersection graphs of axis-parallel segments.Journal of Computational Geometry, 14(1):144–156,
-
[5]
Energy-efficienttargetcoverageinwirelesssensor networks
MihaelaCardei, MyTThai, YingshuLi, andWeiliWu. Energy-efficienttargetcoverageinwirelesssensor networks. In INFOCOM 2005. 24th annual joint conference of the ieee computer and communications societies. proceedings ieee, volume 3, pages 1976–1984. IEEE, 2005. 1 7
work page 2005
-
[6]
Colouring bottomless rectangles and arborescences
Jean Cardinal, Kolja Knauer, Piotr Micek, Dömötör Pálvölgyi, Torsten Ueckerdt, and Narmada Varadarajan. Colouring bottomless rectangles and arborescences, 2020. URL: https://arxiv.org/ abs/1912.05251, arXiv:1912.05251. 2
work page Pith review arXiv 2020
-
[7]
Hiding data in images by simple lsb substitution
Chi-Kwong Chan and Lee-Ming Cheng. Hiding data in images by simple lsb substitution. Pattern recognition, 37(3):469–474, 2004. 1
work page 2004
-
[8]
Howie Choset. Coverage for robotics–a survey of recent results.Annals of mathematics and artificial intelligence, 31:113–126, 2001. 1
work page 2001
Show all 19 references
-
[9]
Geometric packing under nonuniform constraints
Alina Ene, Sariel Har-Peled, and Benjamin Raichel. Geometric packing under nonuniform constraints. SIAM Journal on Computing, 46(6):1745–1784, 2017. 1
2017
-
[10]
Approximating geometric coverage problems
Thomas Erlebach and Erik Jan van Leeuwen. Approximating geometric coverage problems. In Shang- HuaTeng, editor,Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 1267–1276. SIAM, 2008. 1
2008
-
[11]
Hochbaum and Wolfgang Maass
Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI.J. ACM, 32(1):130–136, 1985. 1
1985
-
[12]
Predicting protein-protein interactions from protein domains using a set cover approach
Chengbang Huang, Faruck Morcos, Simon P Kanaan, Stefan Wuchty, Danny Z Chen, and Jesus A Izaguirre. Predicting protein-protein interactions from protein domains using a set cover approach. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(1), 2007. 1
2007
-
[13]
Coloring half-planes and bottomless rectangles.Computational geometry, 45(9):495– 507, 2012
Balázs Keszegh. Coloring half-planes and bottomless rectangles.Computational geometry, 45(9):495– 507, 2012. 2
2012
-
[14]
Coloring intersection hypergraphs of pseudo-disks.Discrete & Computational Geome- try, 64(3):942–964, 2020
Balázs Keszegh. Coloring intersection hypergraphs of pseudo-disks.Discrete & Computational Geome- try, 64(3):942–964, 2020. 2, 6
2020
-
[15]
Covering points with concentric objects
Anil Maheshwari, Saeed Mehrabi, Sasanka Roy, and Michiel Smid. Covering points with concentric objects. In Proceedings of the 32nd Canadian Conference on Computational Geometry, pages 436–452,
-
[16]
Mustafa and Saurabh Ray
Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Dis- crete & Computational Geometry , 44(4):883–895, 2010. URL: http://dx.doi.org/10.1007/ s00454-010-9285-9, doi:10.1007/s00454-010-9285-9. 1
2010 doi
-
[17]
On the chromatic number of geometric hypergraphs.SIAM Journal on Discrete Mathematics, 21(3):676–687, 2007
Shakhar Smorodinsky. On the chromatic number of geometric hypergraphs.SIAM Journal on Discrete Mathematics, 21(3):676–687, 2007. 2
2007
-
[18]
Conflict-free coloring and its applications
Shakhar Smorodinsky. Conflict-free coloring and its applications. InGeometry—Intuitive, Discrete, and Convex: A Tribute to László Fejes Tóth, pages 331–389. Springer, 2013. 2
2013
-
[19]
Building terrain-covering ant robots: A feasibility study
Jonas Svennebring and Sven Koenig. Building terrain-covering ant robots: A feasibility study. Au- tonomous Robots, 16(3):313–332, 2004. 1 8
2004
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.