{"id":"ea3c9eee-948e-40b2-aeaf-e2a623f6bcf3","arxiv_id":"2412.13938","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The contiguous art gallery problem for simple polygons is solvable in O(k* n^5 log n) arithmetic operations, placing the problem in P.","lead":"This paper presents a polynomial-time algorithm for the contiguous art gallery problem, which asks for the fewest guards whose viewing intervals partition a simple polygon's boundary. It is the first efficient solution for this 2024 variant, placing the problem in the complexity class P.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Infinitesimal perturbation arguments in Definition 8 and Remark 41 are load-bearing for Theorem 37 and are not formalized; a degenerate instance could change greedy endpoints.","rationale":"The reader identified the weakest assumption as the informal infinitesimal perturbation arguments in Definition 8 and Remark 41, and I agree that these are the most load-bearing unresolved points in the proof. The combinatorial framework (greedy sequences, fingerprints, edge jumps) is clean and appears sound under the stated axioms. The difficulty is entirely in the geometric translation: lastVisiblePoint must compute a geometrically exact endpoint, and Section 5's proof that either a positive fingerprint, a repetition, or n+1 edge jumps occurs within O(k n^2) revolutions relies on strict separation from pivot lines and on feasible regions that are contained in shadows of a closest vertex. Both strict separation and shadow containment are enforced by infinitesimal perturbations that are described only informally. A concrete degenerate configuration, such as a guard, pivot vertex, and edge endpoint becoming collinear, can make the 'small bit' in Definition 8 or the epsilon in Remark 41 interact with the greedy choice, potentially changing the sequence and breaking the pigeonhole argument over feasible-region/pivot-line pairs. The paper does provide a C++ implementation and reports extensive empirical success, and the result is independently supported by concurrent work merged at SoCG 2025, so the underlying theorem is likely true. But for this manuscript as a standalone proof, the gap is real and should be closed by either a general-position assumption with a perturbation that provably preserves the output, or a fully formalized symbolic perturbation. The reader's CONDITIONAL verdict is therefore appropriate; I would not strengthen or weaken it without seeing such a fix.","tokens_in":36601,"tokens_out":6282,"duration_ms":54811,"concrete_test":"Implement GreedyInterval with exact rational arithmetic and make the perturbed constructions explicit: replace Definition 8's 'small bit' and Remark 41's epsilon by a parameter epsilon chosen symbolically smaller than every distance between combinatorially distinct features of P. Run this version on all simple polygons with n <= 8 whose vertices lie on a small integer grid, and for each instance verify that using epsilon and epsilon/2 yields the identical greedy sequence, identical lastVisiblePoint outputs, and a progress condition within O(k n^2) revolutions. If any instance produces different greedy endpoints or exceeds the bound, the perturbation argument is not valid as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central bound of Theorem 37 depends on the geometric pivot-line analysis in Section 5, and that analysis in turn depends on two informal infinitesimal perturbation arguments. In Definition 8, the blocking polygon B is constructed by backtracking 'a small bit' and choosing distances 'small enough' to avoid self-intersection; the code path of lastVisiblePoint then uses common tangents of F_{i-1} and B, so an incorrect B can change the returned endpoint y and guard g, altering the greedy sequence before the combinatorial optimality conditions (Corollaries 30, 31, 32) ever apply. In Remark 41, the feasible region is replaced by F([y-epsilon, z+epsilon]) for an arbitrary small epsilon, with the assertion that this 'will not impact the other proofs'; this perturbation is used to rule out z lying above L(a,C_{z,i}), which is essential for Lemma 42, Lemma 43, and Proposition 44. The paper does not state a general-position assumption, give a symbolic perturbation scheme, or prove that a single epsilon preserves the greedy sequence while also making the stated geometric inequalities strict. If a degenerate polygon admits no such epsilon, the repeated-pivot-line pigeonhole argument in Theorem 37 collapses, and the polynomial revolution bound is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the contiguous art gallery problem, in which the boundary of a simple polygon must be partitioned into a minimum number of polygonal chains, each visible to some guard in the interior. The authors describe a greedy algorithm that repeatedly computes the longest visible interval from the current boundary point, and they claim that after polynomially many revolutions the greedy sequence contains an optimal solution. The main theoretical results are Theorem 1, an O(k* n^5 log n) arithmetic-operation bound on the real RAM, and Theorem 2, membership in P via a bit-complexity analysis. The combinatorial part (Section 4) establishes structural properties of greedy sequences, including optimality conditions based on fingerprints, repetitions, and edge jumps. The geometric part (Section 5) analyzes feasible regions and pivot lines to prove that a progress condition must occur within O(k n^2) revolutions. Appendices cover vertex-restricted variants, supporting lemmas, and an example showing that the algorithm fails for polygons with holes.","tokens_in":36810,"tokens_out":9065,"duration_ms":81530,"significance":"If the proof is correct, this is a striking result: the contiguous art gallery problem would be one of the few unrestricted art-gallery variants known to be polynomial-time solvable, in contrast to the classical and edge-covering variants that are ∃R-complete. The paper also provides a C++ implementation and a careful bit-complexity argument, which are valuable. The combinatorial framework in Section 4 is elegant and rigorous, and the proposed algorithm is genuinely simple. However, the geometric analysis contains several informal infinitesimal perturbation arguments, and these are load-bearing for the main theorem. The result is therefore significant but not yet fully established as written.","major_comments":[{"comment":"The construction of the blocking polygon B in Definition 8 is not a well-defined geometric procedure: it refers to moving \"a little to the left\", \"back up a small bit\", and choosing distances \"small enough\" without specifying how these choices are made or proving that they can be made simultaneously in every degenerate configuration. Lemma 9 (disjointness of B and F_{i-1}) and Lemma 11 (that L(g,c) is a common tangent) depend on this construction, and therefore the correctness of lastVisiblePoint, Theorem 3, and every downstream step inherits the gap. The paper needs either a formal perturbation scheme (e.g., symbolic perturbation) or a general-position assumption with an argument that the computed greedy endpoint is obtained as a limit of perturbed endpoints.","section":"Definition 8 and Lemma 9-11 (§3.3)"},{"comment":"The assertion that replacing F by F([y-ε,z+ε]) \"will not impact the other proofs\" is load-bearing. Lemma 42 explicitly relies on Remark 41 to rule out z lying above L(a,C_{z,i}), and Lemma 42 is needed for Lemma 43 and Proposition 44, which in turn is essential for Theorem 37. No proof is given that such an ε exists for every relevant step of the greedy sequence while preserving the computed endpoints and guards; for degenerate inputs it is conceivable that every positive ε changes the greedy sequence or fails to make the required geometric inequalities strict. This is a gap in the proof of Theorem 37.","section":"Remark 41 (§5.2)"},{"comment":"Proposition 48 is the core of the \"feasible region below pivot line\" case, but its proof is a long case analysis that relies heavily on figures and unstated geometric properties. For example, the paragraph before Figure 31 asserts that \"both edges in ∂P connected to x will point downwards\" without proof, and Subcase 3.2 relies on the assertion that the ray from the guard through the pivot is contained in Q_i. These claims are not established, and the terminal conditions are asserted rather than derived from the preceding geometry. Since Proposition 48 is used to show that repeated pivot lines lead to a progress condition, Theorem 37 is not fully supported until these cases are proved in detail.","section":"Proposition 48 (§5.3)"}],"minor_comments":[{"comment":"The update rule for j on line 4 uses the condition j ≤ T−2 and then returns intervals {j < i ≤ T}; it is unclear why T−2 appears rather than an index naturally derived from the definition of a revolution, and this off-by-one behavior should be clarified.","section":"Section 2, Algorithm 1"},{"comment":"The proof refers to \"at least k−1 endpoints\" while the statement and the preceding definition of a revolution involve k+1 steps; the indexing should be made consistent and the bound k ≤ k*+1 should be verified directly.","section":"Theorem 21"},{"comment":"The sentence \"Since we only look at blockage (Remark 21)\" refers to a nonexistent remark; the intended reference appears to be Remark 6.","section":"Appendix B.2"},{"comment":"The displayed formulas for t_n and t_d are difficult to verify and appear to contain at least one missing parenthesis; a shorter derivation using a standard line-intersection determinant formula would make the bit-complexity argument more readable.","section":"Lemma 51"},{"comment":"The statement that both edges incident to x \"point downwards\" is not obvious from the definition of x as the furthest point below the pivot line inside the triangle and should be proved or restated as a separate lemma.","section":"Section 5.3, paragraph before Figure 31"}],"recommendation":"major_revision","confidential_remarks":"The authors state in the acknowledgments that this paper was merged with two concurrent works into a SoCG 2025 publication [7]. The editor may wish to verify that this submission does not overlap with that published version in a way that violates the venue's policies. The main technical barrier to acceptance is the formalization of the perturbation arguments; if a rigorous perturbation scheme can be supplied, I would view the result favorably."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know about this paper because it settles a natural open variant of the art gallery problem in P, and does it with a refreshingly simple greedy algorithm rather than heavy algebraic machinery. The contiguous art gallery problem was posed at CCCG 2024; this is one of three independent solutions, and the current text is the merged SoCG version.\n\nWhat's genuinely new: the greedy sequence analysis with fingerprints and edge jumps as combinatorial progress conditions, and the pivot-line argument bounding the number of revolutions. The combinatorial sections are clean and rigorous. The bit complexity section is careful—they track the growth of scalars through the greedy steps and show it's polynomial, which is what puts the problem in P rather than just in the real RAM model. They also ship a C++ implementation, and the empirical note (2M random polygons, all solved within four revolutions) is honest evidence, even if not a proof.\n\nThe soft spots are in the geometric analysis. Definition 8 constructs the blocking polygon B by 'backing up a small bit' and choosing distances 'small enough'; Remark 41 replaces the feasible region with F([y-epsilon, z+epsilon]) for an arbitrary small epsilon and asserts this won't affect other proofs. These are exactly where degenerate configurations could change lastVisiblePoint and thereby alter the greedy sequence. The stress-test note is right that the paper neither states a general-position assumption nor proves a single epsilon preserves greedy behavior. That said, I don't think it's fatal. This pattern appears in many computational geometry papers, and the fix is usually a symbolic perturbation scheme or a more careful limiting argument. The rest of the proof, including Proposition 48's long case analysis, is internally consistent.\n\nThe citation pattern looks fine: they cite the concurrent preprints, the merge paper, and the relevant hardness results. No signs of fitting or circularity; the runtime depends on the unknown optimal k* only as an instance parameter.\n\nBottom line: this deserves a serious referee. The result is significant enough for the community to want it on record, and the gaps are repairable. I'd send it to peer review with a request to formalize the degeneracy handling. A careful referee will earn their keep, but the core contribution is solid.","headline":"A genuinely new polynomial-time result for a natural art gallery variant, with a sound greedy analysis and a fixable degeneracy gap in the geometric proof.","tokens_in":37346,"tokens_out":3529,"would_cite":true,"duration_ms":29372,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the contiguous art gallery problem—partitioning a simple polygon's boundary into the fewest contiguous chains each visible to one guard—is solvable in polynomial time by a simple repeated greedy sweep.","keywords":["art gallery problem","contiguous art gallery","greedy algorithm","simple polygon","boundary partition","visibility polygon","computational geometry","polynomial-time algorithm"],"falsifier":"Construct a simple polygon in which the blocking polygon of Definition 8 necessarily self-intersects for every choice of backtracking distance, causing GreedyInterval's lastVisiblePoint computation to fail; or exhibit a polygon where the greedy sequence runs for more than $c k^* n^2$ revolutions with no positive fingerprint, repetition, or $n+1$ edge jumps for any fixed constant $c$.","tokens_in":36378,"feed_emoji":"🖼️","tokens_out":8381,"duration_ms":64167,"temperature":0.7,"pith_summary":"The paper proves that the contiguous art gallery problem, a 2024 variant of the classical art gallery problem, is solvable in polynomial time. The task is to partition the boundary of a simple polygon into the minimum number of contiguous chains such that each chain is visible from a single guard. The authors give a greedy algorithm that repeatedly takes the longest visible interval from a point on the boundary, and prove that after polynomially many revolutions it must reach an optimal partition. The running time is $O(k^* n^5 \\log n)$ arithmetic operations, where $n$ is the number of vertices and $k^*$ is the size of an optimal solution; a bit-complexity analysis places the problem in the complexity class $\\mathrm{P}$. This stands in contrast to most art gallery variants, which are NP-hard or $\\exists\\mathbb{R}$-complete.","feed_headline":"Greedy sweep puts the contiguous art gallery problem in P","feed_subtitle":"Partition the boundary into few guarded chains, now solvable in O(k* n^5 log n) time.","key_machinery":"The load-bearing object is the greedy interval map $G(x)$ and its iterates, called the greedy sequence. A greedy interval is the longest contiguous boundary chain starting at $x$ that is visible to a single guard; the feasible region of a chain is the intersection of visibility polygons of all points on the chain, and its structure is controlled by pivot lines—lines through pairs of blocking vertices that limit the guard's sight. The argument splits into two cases: when the feasible region lies strictly above the pivot line, any repeated pivot line forces a repetition or an edge jump; when it reaches or dips below the pivot line, a separate analysis shows that some later guard is forced above its own pivot line, eventually triggering a progress condition. The combinatorial spine consists of three optimality certificates—positive fingerprint, periodic repetition, and $n+1$ edge jumps—any of which provably occurs within $O(k n^2)$ revolutions.","core_discovery":"The central claim is Theorem 1: for a simple polygon with $n$ vertices, the contiguous art gallery problem can be solved in $O(k^* n^5 \\log n)$ arithmetic operations, where $k^*$ is the minimum number of chains in an optimal solution. Theorem 2 strengthens this to the bit-complexity RAM model: when the polygon is encoded in $N$ bits, the problem lies in $\\mathrm{P}$. The proof is constructive: the GreedyInterval algorithm computes, for a given boundary point $x$, the farthest boundary point $y$ such that the chain $[x,y]$ is visible to some interior guard. Iterating this map generates a greedy sequence; the paper shows that within $O(k^* n^2)$ revolutions, the sequence must exhibit one of three progress conditions—a positive fingerprint, an exact repetition, or $n+1$ edge jumps—each of which certifies optimality. Repeating this $n+1$ times yields an optimal partition, and the bit-complexity section bounds the size of all computed coordinates, giving the $\\mathrm{P}$ membership.","pith_inferences":["If the authors' conjecture that a constant number of revolutions suffice is correct, the same algorithm would run in $O(n^2 \\log n)$, making the greedy sweep essentially optimal up to the cost of computing visibility polygons.","The pivot-line argument is a potential template for other boundary-covering problems: any greedy map on a circle whose progress is measured by finitely many obstacle lines may admit a polynomial revolution bound by pigeonhole plus local perturbation.","The two informal 'small enough' perturbation arguments are the main gap to a fully formal proof; replacing them with a symbolic perturbation scheme would close the gap without changing the algorithm's structure.","The superpolynomial example for polygons with holes in Appendix C.2 suggests the polynomial bound is specific to hole-free polygons, and any extension to holes would need genuinely new ideas."],"forward_implications":["The contiguous art gallery problem for simple polygons is in $\\mathrm{P}$; it is not NP-hard (assuming $\\mathrm{P} \\neq \\mathrm{NP}$), unlike the classical and edge-covering art gallery problems.","An optimal partition can be found in $O(k^* n^5 \\log n)$ arithmetic operations on a real RAM, and the same bound carries over as a polynomial-time RAM algorithm on an $N$-bit encoding.","Vertex-restricted variants are faster: guarding from vertices runs in $O(n^2 \\log n)$ time, and restricting chain endpoints to vertices runs in $O(n^2 \\log^2 n)$ time.","A practical C++ implementation is available, and empirical tests suggest that the greedy algorithm typically finds an optimal solution within four revolutions, far below the proven bound."],"supporting_citations":[{"why":"supplies the circle-cover minimization framework and the finite-interval greedy analysis that the combinatorial half of the proof adapts","marker":"[20]"},{"why":"gives the linear-time visibility polygon subroutine used to build feasible regions in GreedyInterval","marker":"[10]"},{"why":"provides the polygon-clipping algorithm used to intersect feasible regions in O(n log n) time","marker":"[24]"},{"why":"gives the common-tangent algorithm that computes the last visible point via the blocking polygon","marker":"[3]"},{"why":"establishes that the classical art gallery problem is ∃R-complete, the contrast that makes the polynomial result surprising","marker":"[1]"},{"why":"defines the bit-complexity model used to prove the problem lies in P","marker":"[15]"}],"fun_headline_variants":["Greedy algorithm slides contiguous art gallery into P","Contiguous art gallery solved in polynomial time by greedy sweep","Simple greedy traversal puts contiguous art gallery in P","Art gallery's contiguous cousin is now officially in P"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof relies on being able to perturb the geometry by 'a small bit'—in the construction of the blocking polygon and in excluding edge cases—without changing the greedy algorithm's output, and no rigorous existence proof for such perturbations is given.","fun_headline_variants_meta":{"raw":{"variants":["Greedy algorithm slides contiguous art gallery into P","Contiguous art gallery solved in polynomial time by greedy sweep","Simple greedy traversal puts contiguous art gallery in P","Art gallery's contiguous cousin is now officially in P"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000313,"raw_usage":{"total_tokens":1839,"prompt_tokens":1065,"completion_tokens":774,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":681,"completion_tokens_details":{"reasoning_tokens":711}},"tokens_in":681,"tokens_out":774,"duration_ms":7329,"temperature":1.0,"reasoning_tokens":711,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:38:28.609738+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a simple polygon in which the blocking polygon of Definition 8 necessarily self-intersects for every choice of backtracking distance, causing GreedyInterval's lastVisiblePoint computation to fail; or exhibit a polygon where the greedy sequence runs for more than $c k^* n^2$ revolutions with no positive fingerprint, repetition, or $n+1$ edge jumps for any fixed constant $c$.","supporting_citations":[{"cited_title":"A new algorithm for computing boolean operations on polygons","cited_arxiv_id":null,"evidence_quote":"provides the polygon-clipping algorithm used to intersect feasible regions in O(n log n) time"},{"cited_title":"Common tangents of two disjoint polygons in linear time and constant workspace","cited_arxiv_id":null,"evidence_quote":"gives the common-tangent algorithm that computes the last visible point via the blocking polygon"}],"review_version":1}