Pith. sign in

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 →

arxiv 2412.15567 v2 pith:B5YX4GUJ submitted 2024-12-20 cs.CG

classification cs.CG
keywords contiguousartgalleryanalyticarccoverpolygonseparation3Dcarvingintervalsetpiecewiselinearrationalfunctionspolynomial-timealgorithm
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

The paper establishes that three geometric optimization problems are solvable in polynomial time: the contiguous art gallery problem, in which each guard must watch one contiguous stretch of a polygon's boundary; the minimum-vertex convex polygon separating two sets of line segments; and the problem of carving a 3D polytope from space with the fewest half-plane cuts. All three reduce to a single abstraction, the analytic arc cover problem, a set-cover on the unit circle in which the candidate arcs are infinite and implicitly defined by a 'next-generator' function. The paper shows that when that function is piecewise linear rational, analytic arc cover can be solved in polynomial time on a Turing machine, with the bit complexity of intermediate values controlled. The result answers an open question posed by Shermer about whether art gallery hardness requires guards to watch disjoint boundary intervals.

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.

Watch

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

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

  • 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.
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, and a circularity audit.

Referee Report

4 major / 5 minor

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)
  1. [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.
  2. [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.
  3. [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.
  4. [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)
  1. [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) }.
  2. [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.
  3. [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.'
  4. [Section 1] The first paragraph of Section 1 contains the typo 'contigious'; it should be 'contiguous.'
  5. [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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 4 assumptions · 0 invented entities

The proof rests on standard algebraic and geometric facts, plus domain assumptions about the interval family and the function representation. No parameters are fitted to data, and no new physical entities are introduced.

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)).
    Stated in Section 2.2 after the definition of g; needed so the sup in g(t) is attained and the lifted next-generator is well-defined.
  • standard math Piecewise linear rational functions with first-order radical boundary points are closed under composition and their inverses have comparable bit complexity.
    Used in Lemma 15 and Theorem 11; the paper gives a proof sketch but relies on known algebraic facts about quadratic equations.
  • domain assumption The existential threshold test can be performed by evaluating the function at boundary points and derivative zeros within one period.
    Assumed in the paragraph after Lemma 15; this is a standard fact for piecewise smooth functions, but the paper does not elaborate on the derivative zero computation in the ray representation.
  • 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.
    Foundation of the AnalyticArcCover formulation (Definition 8 and Lemma 7); the paper argues this via greedy optimality but does not give a full proof for circular intervals.

how reviews work

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Contiguous Art Gallery Problem is in {\Theta}(n log n)

    cs.CG 2025-11 unverdicted novelty 8.0 of 10

    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.

  2. The Contiguous Art Gallery Problem is Solvable in Polynomial Time

    cs.CG 2024-12 conditional novelty 8.0 of 10

    The contiguous art gallery problem for simple polygons is solvable in O(k* n^5 log n) arithmetic operations, placing the problem in P.

  3. Simpler and Faster Contiguous Art Gallery

    cs.CG 2025-08 conditional novelty 7.0 of 10

    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

27 extracted references · 17 canonical work pages · cited by 3 Pith papers

  1. [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

  2. [6]

    Introduction to algorithms

    Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms . MIT press, 2022

  3. [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://...

  4. [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

  5. [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

  6. [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

  7. [5]

    Ariful Islam

    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

  8. [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
  1. [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

  2. [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

  3. [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

  4. [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

  5. [12]

    M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman, 1979

  6. [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

  7. [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

  8. [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

  9. [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

  10. [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

  11. [18]

    Art gallery theorems and algorithms

    Joseph O'rourke. Art gallery theorems and algorithms . Oxford University Press, Inc., 1987

  12. [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

  13. [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...

  14. [21]

    Advanced problem 6369

    Joseph O’Rourke. Advanced problem 6369. Amer. Math. Monthly , 88(10):769, 1981

  15. [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...

  16. [23]

    Computational Geometry

    Michael Ian Shamos. Computational Geometry . PhD thesis, Yale University, 1978. URL: http://euro.ecom.cmu.edu/people/faculty/mshamos/1978ShamosThesis.pdf

  17. [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

  18. [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-...

  19. [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-...

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.