REVIEW 4 major objections 5 minor 3 cited by
The Analytic Arc Cover Problem and its Applications to Contiguous Art Gallery, Polygon Separation, and Shape Carving
T0 review · 4 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read The paper proves that three geometric optimization problems — the contiguous art gallery problem, the minimum-vertex separation of two segment sets, and minimizing half-plane cuts to carve a 3D polytope — are all solvable in polynomial…
desk verdict A genuine framework for infinite arc covers with polynomial results for three geometry problems, but the SegmentSeparation reduction is sketched enough that the main new claim needs a serious referee. 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 object is the analytic arc cover problem and its lifted next-generator. Given a function $g: S^1 \to S^1$ that returns the counterclockwise far endpoint of the farthest arc covering a point, the problem asks for the minimum $k$ such that $[x, g(x)) \cup [g(x), g^2(x)) \cup \cdots \cup [g^{k-1}(x), g^k(x))$ equals $S^1$ for some $x$. The algorithm lifts $g$ to a monotone, proper map $\tilde{g}$ on $\mathbb{Z} \times S^1$, composes it $k$ times, and performs an existential threshold test for each $k$; the test succeeds iff there is an $x$ with $\tilde{g}^k(x) \ge (1,x)$. When $g$ is piecewise linear rational — in either the unit-interval or ray representation — the compositions stay in the same family, the number of pieces grows polynomially, and the boundary points remain first-order radicals, so the threshold test is polynomial-time. This is the machinery all three reductions feed into.
What would settle it
A small rational-coordinate instance of SegmentSeparation whose optimal separating polygon, found by exhaustive search over all candidate tangent-line arrangements, cannot be reproduced by the greedy sweep of Theorem 27 would disprove the reduction and hence Theorem 2.
Extended reading notes
Core claim
The central discovery is that three previously open problems — ContiguousArtGallery, SegmentSeparation, and minimum 3D half-plane carving — are all in $\mathsf{P}$. The proof route is a reduction to AnalyticArcCover: each problem's candidate covering pieces are encoded as arcs on $S^1$ whose far endpoints are given by a next-generator function $g$, and the optimization becomes the smallest $k$ such that some $k$-fold iterate of $g$ covers the circle. The technical engine is that piecewise linear rational functions are closed under composition, and their $k$-fold iterates have only polynomially many boundary points whose bit complexity stays polynomial, so each existential threshold test ('does the $k$-th iterate cover the circle?') can be answered in polynomial time. With this, the paper proves Theorem 1, Theorem 2, and Theorem 3.
Load-bearing premise
The reduction for SegmentSeparation assumes that every optimal separating polygon can be obtained by a greedy counterclockwise sweep in which the next cut is determined by the first 'stop intersecting' event, but the paper presents this modeling equivalence only by a high-level description and does not give a formal proof, while conceding that a naive greedy edge-selection rule is not known to be optimal for the classic PolygonSeparation problem.
Editorial extensions
If this is right
- ContiguousArtGallery is in $\mathsf{P}$, and the NP-hardness of general art gallery guarding genuinely depends on allowing a guard to watch disjoint boundary intervals.
- SegmentSeparation is in $\mathsf{P}$, which subsumes the earlier point and polygon separation results and handles arbitrary line-segment obstacles.
- The minimum number of half-plane cuts needed to carve a 3D polytope is computable in polynomial time, closing the optimization version of the carving problem.
- The arc-cover framework extends to contiguous guarding of polygons with holes, as noted in Remark 24.
- All running times are polynomial in the input bit complexity, not just in a real-RAM model.
Reading between the lines
- The same analytic arc cover recipe may apply to other geometric covering problems whose candidate regions are generated by a monotone 'next' rule, since the only requirements are closure under composition and an existential threshold test.
- Because the proof keeps intermediate numbers at first-order radical complexity, it sidesteps the sum-of-square-roots bottleneck that often blocks Turing-machine results for geometric optimization, suggesting a general design principle for $\mathsf{P}$ membership proofs.
- If the greedy sweep model in Theorem 27 misses some optimal separating polygons, the arc-cover reduction for SegmentSeparation would need a richer state space; a brute-force search on small instances would settle this quickly.
- The result sharpens the boundary between $\mathsf{P}$ and $\exists\mathbb{R}$-complete in geometric covering: the deciding factor is not simply whether candidate placements are continuous, but whether the covering function has an analytic representation that composes cleanly.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the AnalyticArcCover problem, an infinite-arc variant of circular interval cover in which the arcs are generated by a next-generator function g: S^1 -> S^1, and proves that when g is piecewise linear rational, the problem is solvable in polynomial time on a Turing machine (Theorems 9 and 11). It then claims three applications: ContiguousArtGallery is in P (Theorem 1), SegmentSeparation is in P (Theorem 2), and minimizing the number of half-plane cuts to carve a 3D polytope is in P (Theorem 3). The first two results are obtained by reducing each problem to AnalyticArcCover, and the third by reducing to SegmentSeparation. The paper also situates its work relative to concurrent independent results on contiguous art gallery.
Significance. If fully established, the paper would answer an open problem posed by Shermer at CCCG '24, give the first P-membership result for SegmentSeparation, and resolve the optimization version of 3D half-plane carving left open in earlier work. The AnalyticArcCover framework is a useful unifying device, and the composition-closure and bit-complexity arguments in Section 2 (Lemma 13, Lemma 15, Theorem 11) are clean and constitute a genuine algorithmic contribution. The paper is also commendably candid about concurrent work and its relation to the combined paper [6]. However, the reduction sections, especially Section 4 and Section 5, contain substantial proof gaps that prevent the main theorems from being considered established in the present form.
major comments (4)
- [Section 4, Theorem 27] The reduction is built on an unproved greedy-sweep equivalence. The proof describes a sweep that stops at the first 'about to stop' event, asserts that the next cut takes one of two forms, and then says 'we take the first of all potential next half-planes required to fully cover each line segment not covered by the current half-plane.' It never provides an exchange argument showing that replacing an arbitrary next side of an optimal separating polygon by this first-event side does not increase the number of sides. The paper's own preamble in Section 4 states that for PolygonSeparation and SegmentSeparation 'we are unable to prove that this is the case' for the analogous greedy edge-selection rule. Without such an argument, the minimum of the constructed AnalyticArcCover instance could be strictly larger than the minimum separating polygon, so Theorem 2 is not established.
- [Section 4, Definition 4] The next-generator in AnalyticArcCover is defined as a function g: S^1 -> S^1 that depends only on the current point t (Definition 4). In the proposed reduction, however, the first-event half-plane depends on the set of segments not yet covered by previous half-planes, that is, on the entire history of the sweep. The proof does not show that this first-event map is independent of prior cuts or that it can be encoded as a state-independent function of the current normal vector alone. If the map is history-dependent, the object constructed is not an instance of AnalyticArcCover as defined, and Theorem 11 cannot be applied. The proof needs either a formal state-independence argument or an explicit extension of the framework that tracks state.
- [Section 5, Lemma 29] Lemma 29 asserts that the only way to reduce the number of half-plane cuts is to merge coplanar half-planes, and that solving the 2D Polygon Separating problem on each coplanar partition yields a global minimum. The proof is a single sentence: 'For a face to be carved, there must be a set of co-planar half-planes covering the face. Hence, this allows us to reduce the optimization variant to the two-dimensional Polygon Separating problem.' This does not justify why a half-plane lying in one plane cannot help carve a face lying in another plane, nor why the optimal global solution decomposes independently over coplanar partitions. Since Theorem 3 relies on Lemma 29, this needs a rigorous proof.
- [Section 3, Lemma 20 and Theorem 23] The case analysis in Lemma 20 is not presented as a complete proof. The statement 'We claim that one of these intersection points forms an optimal guard point' is followed by a list of cases that are described in words and figures, but no formal argument is given that the enumerated lines exhaust all possible locations of an optimal guard point, nor that the chosen candidate is always optimal. Because Theorem 23 uses Lemma 20 through Lemma 22 to define the next-generator for ContiguousArtGallery, the correctness of Theorem 1 depends on closing this gap.
minor comments (5)
- [Definition 4] The formula for g(t) uses the variable a without introducing it; the definition should quantify over left endpoints a of arcs, e.g., g(t) = sup{ b : [a,b) in I and t in [a,b) }.
- [Lemma 7] The sentence 'Observe that by the greedy algorithm has the counter-clockwise point of I'_j farther than the counter-clockwise point of I_j' is ungrammatical and should be rephrased to clarify the comparison between the greedy intervals and the optimal intervals.
- [Section 3, Theorem 23 proof] The sentence 'That is, g takes a value t in [0,1), proof, we will assume e_i is fixed' contains a stray fragment 'proof' and should read 'For the proof, we will assume e_i is fixed.'
- [Section 1] The first paragraph of Section 1 contains the typo 'contigious'; it should be 'contiguous.'
- [Section 4, Theorem 27 statement] The statement of Theorem 27 refers to 'the minimum carving by line segments problem,' but the reduction is for SegmentSeparation; the terminology should be aligned with the rest of the section.
Circularity Check
No significant circularity: the AnalyticArcCover framework is internally developed, the one load-bearing self-citation to [25] is an independent parameter-free characterization, and the main weakness (Theorem 27's greedy-sweep equivalence) is a correctness gap rather than a circular derivation.
full rationale
The paper's derivation chain reduces ContiguousArtGallery, SegmentSeparation, and 3D half-plane carving to AnalyticArcCover (Definition 8), then solves AnalyticArcCover for piecewise linear rational next-generators (Theorem 11). I find no step in which a claimed result is identical to its own input by construction. Theorem 11 is an internal algorithm: it composes the lifted next-generator and performs existential threshold tests, and its polynomial-time claim is supported by Lemma 15; no fitted parameter is later renamed as a prediction. The ContiguousArtGallery reduction (Theorem 23) constructs g from visibility geometry; the proof that the constructed f equals g is an exchange/contradiction argument, not a definitional identity. For SegmentSeparation, Section 4 openly concedes that greedy edge selection is not known to be optimal for PolygonSeparation and SegmentSeparation, and the proof of Theorem 27 is a high-level sweep description rather than a formal exchange argument showing every optimal separating polygon is a greedy first-event sequence. This is a soundness gap in the claimed reduction, but it is not circularity: AnalyticArcCover is not defined in terms of the segment-separation optimum, and the equality is asserted rather than derived by construction. The only load-bearing self-citation is Theorem 28 from the authors' prior paper [25], used in Lemma 29 to reduce 3D carving to Polygon Separation; that theorem is a parameter-free characterization whose stated assumptions do not include the target minimization result, so under the review rules it counts as independent evidence and does not raise the circularity score. No external benchmark is reverse-engineered and no data are fitted. The correct circularity verdict is therefore no circularity; the Theorem 27 proof gap is a correctness risk to be weighed separately.
Assumptions & free parameters
assumptions (4)
- domain assumption The interval family I has a next-generator g defined by a genuine maximum: for every t, there is an interval [a,b) in I containing [t,g(t)).
- standard math Piecewise linear rational functions with first-order radical boundary points are closed under composition and their inverses have comparable bit complexity.
- domain assumption The existential threshold test can be performed by evaluating the function at boundary points and derivative zeros within one period.
- standard math The minimum number of arcs needed to cover S1 for an interval family equals the minimum over x of the greedy sequence length using the next-generator.
Cite this review
Pith. "Pith review of The Analytic Arc Cover Problem and its Applications to Contiguous Art Gallery, Polygon Separation, and Shape Carving." pith.science (2026). https://pith.science/paper/B5YX4GUJ
@misc{pith2026241215567,
author = {Pith},
title = {Pith review of: The Analytic Arc Cover Problem and its Applications to Contiguous Art Gallery, Polygon Separation, and Shape Carving},
year = {2026},
howpublished = {\url{https://pith.science/paper/B5YX4GUJ}},
note = {Machine review of arXiv:2412.15567}
}
abstract
We show the following problems are in $\textsf{P}$: 1. The contiguous art gallery problem -- a variation of the art gallery problem where each guard can protect a contiguous interval along the boundary of a simple polygon. This was posed at the open problem session at CCCG '24 by Thomas C. Shermer. 2. The polygon separation problem for line segments -- For two sets of line segments $S_1$ and $S_2$, find a minimum-vertex convex polygon $P$ that completely contains $S_1$ and does not contain or cross any segment of $S_2$. 3. Minimizing the number of half-plane cuts to carve a 3D polytope. To accomplish this, we study the analytic arc cover problem -- an interval set cover problem over the unit circle with infinitely many implicitly-defined arcs, given by a function.
Forward citations
Cited by 3 Pith papers
-
The Contiguous Art Gallery Problem is in {\Theta}(n log n)
The Contiguous Art Gallery problem is solved in Θ(n log n) time in the real RAM model, improving the prior O(k n^5 log n) upper bound and proving an Ω(n log n) lower bound.
-
The Contiguous Art Gallery Problem is Solvable in Polynomial Time
The contiguous art gallery problem for simple polygons is solvable in O(k* n^5 log n) arithmetic operations, placing the problem in P.
-
Simpler and Faster Contiguous Art Gallery
The contiguous art gallery problem is solvable in O(k n^2 log^2 n) time using O(n^2) candidate greedy start points and an O(log^2 n)-time farthest-visible-chain query.
Reference graph
Works this paper leans on
-
[25]
Complexity of the boundary-guarding art gallery problem
Jack Stade. Complexity of the boundary-guarding art gallery problem. CoRR , abs/2210.12817, 2022. https://arxiv.org/abs/2210.12817 arXiv:2210.12817 , https://doi.org/10.48550/ARXIV.2210.12817 doi:10.48550/ARXIV.2210.12817
-
[6]
Introduction to algorithms
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms . MIT press, 2022
2022
-
[1]
Irrational guards are sometimes needed
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. Irrational guards are sometimes needed. In Boris Aronov and Matthew J. Katz, editors, 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia , volume 77 of LIPIcs , pages 3:1--3:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2017. https://...
-
[2]
The art gallery problem is \( \) R -complete
Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is \( \) R -complete. J. ACM , 69(1):4:1--4:70, 2022. https://doi.org/10.1145/3486220 doi:10.1145/3486220
doi:10.1145/3486220 2022
-
[3]
The art gallery theorem: its variations, applications and algorithmic aspects
Alok Aggarwal. The art gallery theorem: its variations, applications and algorithmic aspects . PhD thesis, Johns Hopkins University, 1984
work page 1984
-
[4]
Finding minimal convex nested polygons
Alok Aggarwal, Heather Booth, Joseph O'Rourke, Subhash Suri, and Chee - Keng Yap. Finding minimal convex nested polygons. Inf. Comput. , 83(1):98--110, 1989. https://doi.org/10.1016/0890-5401(89)90049-7 doi:10.1016/0890-5401(89)90049-7
-
[5]
Syed Ishtiaque Ahmed, Masud Hasan, and Md. Ariful Islam. Cutting a convex polyhedron out of a sphere. Graphs Comb. , 27(3):307--319, 2011. https://doi.org/10.1007/s00373-011-1018-1 doi:10.1007/s00373-011-1018-1
-
[7]
Cutting out polygons with lines and rays
Ovidiu Daescu and Jun Luo. Cutting out polygons with lines and rays. Int. J. Comput. Geom. Appl. , 16(2-3):227--248, 2006. https://doi.org/10.1142/S0218195906002014 doi:10.1142/S0218195906002014
Show all 27 references
-
[8]
Demaine, Martin L
Erik D. Demaine, Martin L. Demaine, and Craig S. Kaplan. Polygons cuttable by a circular saw. Comput. Geom. , 20(1-2):69--84, 2001. https://doi.org/10.1016/S0925-7721(01)00036-0 doi:10.1016/S0925-7721(01)00036-0
2001 doi
-
[9]
Demaine, Joseph S
Erik D. Demaine, Joseph S. B. Mitchell, and Joseph O’Rourke. Problem 33: Sum of Square Roots . URL: https://topp.openproblem.net/p33
-
[10]
Cutting out polygons with a circular saw
Adrian Dumitrescu and Masud Hasan. Cutting out polygons with a circular saw. Int. J. Comput. Geom. Appl. , 23(2):127--140, 2013. https://doi.org/10.1142/S0218195913600030 doi:10.1142/S0218195913600030
2013 doi
-
[11]
Preparata
Herbert Edelsbrunner and Franco P. Preparata. Minimum polygonal separation. Inf. Comput. , 77(3):218--232, 1988. https://doi.org/10.1016/0890-5401(88)90049-1 doi:10.1016/0890-5401(88)90049-1
1988 doi
-
[12]
M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman, 1979
1979
-
[13]
Linear time algorithms on circular-arc graphs
Wen-Lian Hsu and Kuo-Hui Tsai. Linear time algorithms on circular-arc graphs. Information Processing Letters , 40(3):123--129, 1991
1991
-
[14]
Jaromczyk and Miros aw Kowaluk
Jerzy W. Jaromczyk and Miros aw Kowaluk. Sets of lines and cutting out polyhedral objects. Comput. Geom. , 25(1-2):67--95, 2003. https://doi.org/10.1016/S0925-7721(02)00131-1 doi:10.1016/S0925-7721(02)00131-1
2003 doi
-
[15]
Guarding the walls of an art gallery
Aldo Laurentini. Guarding the walls of an art gallery. Vis. Comput. , 15(6):265--278, 1999. https://doi.org/10.1007/S003710050177 doi:10.1007/S003710050177
1999 doi
-
[16]
D. T. Lee and Arthur K. Lin. Computational complexity of art gallery problems. IEEE Trans. Inf. Theory , 32(2):276--282, 1986. https://doi.org/10.1109/TIT.1986.1057165 doi:10.1109/TIT.1986.1057165
1986
-
[17]
The contiguous art gallery problem is solvable in polynomial time, 2024
Magnus Christian Ring Merrild, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, and Rolf Svenning. The contiguous art gallery problem is solvable in polynomial time, 2024. URL: https://arxiv.org/abs/2412.13938, https://arxiv.org/abs/2412.13938 arXiv:2412.13938
2024 arXiv
-
[18]
Art gallery theorems and algorithms
Joseph O'rourke. Art gallery theorems and algorithms . Oxford University Press, Inc., 1987
1987
-
[19]
Visibility
Joseph O'Rourke. Visibility. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, Second Edition , pages 643--663. Chapman and Hall/CRC, 2004. https://doi.org/10.1201/9781420035315.CH28 doi:10.1201/9781420035315.CH28
2004 doi
-
[20]
Overmars and Emo Welzl
Mark H. Overmars and Emo Welzl. The complexity of cutting paper (extended abstract). In Proceedings of the First Annual Symposium on Computational Geometry, Baltimore, Maryland, USA, June 5-7, 1985 , pages 316--321. ACM , 1985. https://doi.org/10.1145/323233.323274 doi:10.1145...
1985
-
[21]
Advanced problem 6369
Joseph O’Rourke. Advanced problem 6369. Amer. Math. Monthly , 88(10):769, 1981
1981
-
[22]
Robson, Jack Spalding - Jamieson, and Da Wei Zheng
Eliot W. Robson, Jack Spalding - Jamieson, and Da Wei Zheng. Carving polytopes with saws in 3d. In Rahnuma Islam Nisha, editor, Proceedings of the 36th Canadian Conference on Computational Geometry, CCCG 2024, Brock University, St. Catharines, Ontario, Canada, July 17 - August...
2024
-
[23]
Computational Geometry
Michael Ian Shamos. Computational Geometry . PhD thesis, Yale University, 1978. URL: http://euro.ecom.cmu.edu/people/faculty/mshamos/1978ShamosThesis.pdf
1978
-
[24]
Thomas C. Shermer. Recent results in art galleries (geometry). Proc. IEEE , 80(9):1384--1399, 1992. https://doi.org/10.1109/5.163407 doi:10.1109/5.163407
1992 doi
-
[26]
Approximation algorithms for cutting out polygons with lines and rays
Xuehou Tan. Approximation algorithms for cutting out polygons with lines and rays. In Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings , volume 3595 of Lecture Notes in Computer Science , pages 534-...
2005 doi
-
[27]
o rg - R \
Jorge Urrutia. Art gallery and illumination problems. In J \" o rg - R \" u diger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry , pages 973--1027. North Holland / Elsevier, 2000. https://doi.org/10.1016/B978-044482537-7/50023-1 doi:10.1016/B978-044482537-...
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.