{"id":"cde6aee6-147f-44df-8811-8fb4aabe0114","arxiv_id":"2412.15567","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Three geometric problems, contiguous art gallery, segment separation, and 3D half-plane carving minimization, are shown to be in P via the analytic arc cover framework.","lead":"This paper proves three geometric optimization problems, including a contiguous art gallery variant and a polygon separation problem, are solvable in polynomial time. It introduces a new framework, the analytic arc cover problem, for covering a circle with infinitely many implicitly defined arcs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2 rests on the unproved greedy-sweep equivalence in Theorem 27; the paper's own admission that greedy edge selection is not known optimal for PolygonSeparation leaves SegmentSeparation's central reduction unsupported.","rationale":"The analytic arc cover framework (Theorems 8-11) is a genuine contribution and appears internally consistent: closure of piecewise linear rational functions under composition, the bit-complexity bounds in Lemmas 13-15, and the polynomial existential threshold test are all given with the core details. For ContiguousArtGallery, Theorem 23 supplies a substantially more detailed reduction, and independent concurrent work (Merrild et al., Biniaz et al., and the combined SoCG paper [6]) supports P-membership, so I do not see a load-bearing gap in Theorem 1. The 3D carving result (Theorem 3) reduces to SegmentSeparation via Lemma 29, which is plausible but inherits the risk. The single most load-bearing concern is the proof of Theorem 27: the text asserts rather than proves that greedy sweeping over half-plane orientations captures all optimal separating polygons. This matches the reader's weakest assumption, so I agree with the conditional verdict. I would not reject: the reduction is likely fillable, because the interval-hitting view of separating half-planes suggests a standard exchange argument, and the analytic arc cover machinery itself is sound. The concrete test described above would either find a counterexample or leave only a proof obligation; in the latter case, conditional acceptance with a request for a formal proof is appropriate.","tokens_in":16395,"tokens_out":17663,"duration_ms":180998,"concrete_test":"Formalize the intended equivalence as a minimum piercing problem: for each point z on an outer segment, let I_z = {theta in S^1 : z lies outside the supporting half-plane of the inner polygon with outward normal theta}; prove that a set of side normals Theta is a separating polygon iff Theta pierces every I_z and Theta is not contained in any closed semicircle. Then, on all small instances (e.g., inner polygons with 3-5 vertices and 2-4 outer segments, rational coordinates), compute the true minimum separating polygon by exhaustive enumeration of candidate side normals through segment endpoints and tangencies, and compare it with the value returned by the AnalyticArcCover instance built from Theorem 27's next-generator. A single mismatch would refute Theorem 2; if many random instances match, the missing piece is reduced to a proof obligation rather than a counterexample.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Theorem 27: SegmentSeparation is reduced to AnalyticArcCover by mapping each current half-plane normal to the half-plane obtained by sweeping counter-clockwise and stopping at the first 'about to stop' event among uncovered segments. For Theorem 2 to follow, every optimal separating polygon must be recoverable from a sequence of such first-event half-planes, and the minimum number of these half-planes must equal the minimum number of polygon sides. The proof is a high-level sketch: it lists two event types, asserts that the next-generator is piecewise linear rational, and does not give the exchange argument showing that replacing an arbitrary next side by the first-event side never increases the optimum. It also does not show that this first-event map is independent of the prior choice of cuts, even though the state-independent definition of the next-generator (Definition 4) requires exactly that. The concern is sharpened by the paper's own concession in the first paragraph of Section 4 that a naive greedy edge-selection rule is not known to be optimal for PolygonSeparation and SegmentSeparation. If some optimal separating polygon uses a side before the first stop event, the analytic arc cover could overestimate the answer, and Theorem 2 (and Theorem 3 via Lemma 29) would not be established. No independent verification of the SegmentSeparation reduction is provided in this manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16674,"tokens_out":7555,"duration_ms":60488,"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":[{"comment":"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":"Section 4, Theorem 27"},{"comment":"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":"Section 4, Definition 4"},{"comment":"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":"Section 5, Lemma 29"},{"comment":"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.","section":"Section 3, Lemma 20 and Theorem 23"}],"minor_comments":[{"comment":"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) }.","section":"Definition 4"},{"comment":"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":"Lemma 7"},{"comment":"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":"Section 3, Theorem 23 proof"},{"comment":"The first paragraph of Section 1 contains the typo 'contigious'; it should be 'contiguous.'","section":"Section 1"},{"comment":"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.","section":"Section 4, Theorem 27 statement"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The analytic arc cover machinery is real and worth knowing: for piecewise linear rational next-generators, the composition/threshold-test algorithm gives polynomial time in the Turing model, and the art gallery reduction is worked out in detail. But the paper's headline new result, Theorem 2 (SegmentSeparation in P), rests on a reduction in Theorem 27 that is more of a sketch than a proof, and the paper itself concedes the greedy edge-selection rule is not known optimal for the related PolygonSeparation. That is a load-bearing gap, not a cosmetic one.\n\nWhat's genuinely new: the AnalyticArcCover problem and the observation that PLR functions are closed under composition and support existential threshold tests cleanly. The reduction for ContiguousArtGallery is detailed and likely correct, and the extension to polygons with holes is plausible. The 3D carving result (Theorem 3) depends on Theorem 2, so it inherits the gap; Lemma 29 itself is a reasonable reduction but is also asserted rather than fully argued.\n\nThe soft spots are real but localized. Theorem 27's proof is a paragraph that describes a sweep with two event types, says the resulting map is piecewise linear rational, and then says 'rather than carefully handle the cases, we take the first of all potential next half-planes' and asserts that is a PLR function via Lemma 14. There is no exchange argument showing that replacing an arbitrary next side by the first-event side never increases the optimum. The stress-test note is on target: the definition of the next-generator in AnalyticArcCover requires state independence, and no proof is given that the first-event map is independent of the prior cut. The paper's own admission in Section 4 first paragraph that greedy edge selection is not known optimal for PolygonSeparation sharpens the concern. This is not a manufactured flaw; it is the central reduction of the paper's most important new theorem.\n\nThe bit-complexity argument in Section 2 is careful about first-order radical numbers and the two-square-root comparison issue, which is a nice touch. The citation to [25] for the carveability characterization is independent prior work, so no circularity there.\n\nBottom line: this paper deserves a serious referee, but the referee should be told that Theorem 27 needs a complete proof or a clear statement of the exchange argument before Theorem 2 is accepted. As written, I would not stake a new result on the SegmentSeparation claim. The AnalyticArcCover framework and the art gallery section are worth publishing even if the separation reduction has to be deferred. Bring it to reading group, but read it with a pencil.","headline":"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.","tokens_in":704,"tokens_out":1423,"would_cite":true,"duration_ms":33465,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["contiguous art gallery","analytic arc cover","polygon separation","3D carving","interval set cover","piecewise linear rational functions","polynomial-time algorithm"],"falsifier":"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.","tokens_in":16229,"feed_emoji":"📐","tokens_out":9558,"duration_ms":74507,"temperature":0.7,"pith_summary":"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.","feed_headline":"Arc-cover method puts three geometry problems in P","feed_subtitle":"A single analytic interval-cover abstraction settles art gallery, segment separation, and 3D carving.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the minimum polygon separation problem and proves the minimal separating polygon is convex; SegmentSeparation generalizes this.","marker":"[4]"},{"why":"Solves the point separation problem, a special case of SegmentSeparation, and supplies the classical baseline.","marker":"[13]"},{"why":"Shows the classical art gallery problem is ∃R-complete, which motivates why a polynomial-time contiguous variant is surprising.","marker":"[2]"},{"why":"Concurrent work provides a real-RAM polynomial algorithm for ContiguousArtGallery and poses P membership as open.","marker":"[20]"},{"why":"Concurrent work also proves a polynomial-time algorithm for contiguous boundary guarding; the paper contrasts its own framework.","marker":"[7]"},{"why":"Proves the half-plane carveability characterization (Theorem 28) that the carving reduction relies on.","marker":"[25]"}],"fun_headline_variants":["One arc cover framework to rule three geometry problems","Analytic arc cover settles art gallery, separation, carving","Three previously open problems now in P via arc cover","Arc-cover reduction solves art, separation, carving in P"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["One arc cover framework to rule three geometry problems","Analytic arc cover settles art gallery, separation, carving","Three previously open problems now in P via arc cover","Arc-cover reduction solves art, separation, carving in P"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001222,"raw_usage":{"total_tokens":4991,"prompt_tokens":877,"completion_tokens":4114,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":493,"completion_tokens_details":{"reasoning_tokens":4049}},"tokens_in":493,"tokens_out":4114,"duration_ms":22144,"temperature":1.0,"reasoning_tokens":4049,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:19:55.407643+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Linear time algorithms on circular-arc graphs","cited_arxiv_id":null,"evidence_quote":"Solves the point separation problem, a special case of SegmentSeparation, and supplies the classical baseline."},{"cited_title":"Overmars and Emo Welzl","cited_arxiv_id":null,"evidence_quote":"Concurrent work provides a real-RAM polynomial algorithm for ContiguousArtGallery and poses P membership as open."},{"cited_title":"Cutting out polygons with lines and rays","cited_arxiv_id":null,"evidence_quote":"Concurrent work also proves a polynomial-time algorithm for contiguous boundary guarding; the paper contrasts its own framework."}],"review_version":1}