{"id":"fe6ff73c-221c-4bab-916c-25f9494883b4","arxiv_id":"2508.09734","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"This paper presents a simpler and faster algorithm for the contiguous art gallery problem, a new 2025 variant of the classic museum-guard question. It improves the best known running time from O(k n^5 log n) to O(k n^2 log^2 n), where n is the number of polygon vertices and k is the minimum number of guards.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.9's proof asserts a false equality for the visibility core of left-turning shortest paths; the bad-guard query in Lemma 6.8 depends on it.","rationale":"Agree with the reader: the weakest assumption is indeed Lemma 4.9. The central algorithm's correctness depends on the greedy subroutine returning a genuine maximal guarded chain at every step. The good-guard case is covered by Corollary 4.7 and GP, but the bad-guard case is entirely built on Lemma 4.9. The proof's key equality is not a consequence of left-turning; the three-edge example demonstrates that. If the polygon context somehow makes the equality true, it needs an explicit argument; none is given. The other potential issues (Theorem 5.4's angle conclusion, Lemma 6.6 general position) are either less central or more easily patched. Accordingly, the paper remains CONDITIONAL: the advertised O(k n^2 log^2 n) bound is plausible but not established until Lemma 4.9 is either proved with the missing intermediate-halfplane argument or replaced. No adjustment to the reader's verdict is needed.","tokens_in":12920,"tokens_out":17260,"duration_ms":181518,"concrete_test":"Generate a simple polygon containing a reflex chain such that the shortest path from v to u has three edges (e.g., a U-shaped corridor with u=(0,10), v=(0,0) and forced path (0,0)->(5,0)->(5,10)->(0,10)). Compute Sv, ℓu, ℓv, and PE. Take the first and last intersection points of ℓu with ∂PE and test each point w: (i) is w left of every intermediate supporting line of Sv? (ii) does the segment w-q stay inside P for every q∈[u,v]? If any w passes the first/last halfplane test but fails (i) or (ii), Lemma 4.9 is false. Independently, note the example chain above already shows the proof's asserted equality is not a general property of left-turning chains.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 4.9 (Section 4.2) is the load-bearing step for the bad-guard branch of the query structure in Lemma 6.8. Its proof states: 'Since g can see both u and v, the edges of Sv form a left-turning chain ... It follows that the visibility core of Sv is the intersection of the halfplanes left of ℓu and ℓv.' That 'it follows' is false for left-turning chains in general: for the chain (0,0)->(10,0)->(10,10)->(0,10), the visibility core is {y≥0, x≤10, y≤10}, while the intersection of the first and last halfplanes is just {0≤y≤10}; the middle edge's halfplane adds a constraint. The proof supplies no argument that in the shortest-path context the boundary-chain core PE implies all intermediate Sv halfplanes. If an intermediate halfplane is not implied, the point g* computed as a first/last intersection of ℓu with PE may fail to lie in the true visibility core of Pv, and by Observation 2.2 it need not see [u,v]. Lemma 6.8 then may output a maximal chain [u,v] that no single guard actually sees, causing the greedy algorithm in Theorem 7.1 to return a set of 'guards' that do not guard the boundary. This is the single most load-bearing unproved geometric claim; the other gaps cited (Theorem 5.4 angle inference, Proposition 4.3) are secondary.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an O(k n^2 log^2 n)-time, O(n^2)-space algorithm for the contiguous art gallery problem. The approach is to show that there is an optimal solution containing a guard whose chain starts in an O(n^2)-size candidate set U_P, and to build a data structure that, for any start point u, returns the maximal chain [u,v] guardable by a single contiguous guard in O(log^2 n) time. The structural core is a classification of guards into \"good\" and \"bad\": good guards are replaced by vertices of the arrangement of edge-supporting lines, while bad guards are handled through a claim about the visibility core of the shortest path between u and v. The main theorem follows by running the greedy algorithm from every candidate start point.","tokens_in":13108,"tokens_out":7335,"duration_ms":84355,"significance":"If correct, this is a substantial improvement: the fastest previous algorithm runs in O(k n^5 log n) time, and the proposed solution is both simpler and faster. The paper has genuine strengths: it presents an explicit O(n^2) candidate set, uses standard shortest-path and ray-shooting primitives, and avoids fitted parameters or black-box quantifier elimination. The greedy optimality argument (Theorem 7.1) is a standard exchange argument and is plausible. However, the correctness of the whole construction depends on several geometric assertions that are not derived, the most serious being Lemma 4.9. Because the bad-guard branch of the query data structure (Lemma 6.8) rests on this lemma, the central claim is not currently established.","major_comments":[{"comment":"The proof states: \"the edges of Sv form a left-turning chain ... It follows that the visibility core of Sv is the intersection of the halfplanes left of ℓu and ℓv.\" This equality is false for arbitrary left-turning chains. For example, for the chain (0,0)->(10,0)->(10,10)->(0,10), the visibility core is {y≥0, x≤10, y≤10}, whereas the intersection of the first and last halfplanes is only {0≤y≤10}; the middle edge imposes an extra constraint. The proof supplies no argument that in the shortest-path context of a simple polygon, and with g seeing both u and v, the intermediate halfplanes are implied by the two extremes. This is load-bearing: Lemma 6.8's bad-guard case uses Lemma 4.9 to certify that the first/last intersection points g* of ℓu with PE lie in the true visibility core of Pv. If that certification fails, the query may output a maximal chain [u,v] that no single guard actually see","section":"Section 4.2, Lemma 4.9"},{"comment":"In the case where G contains only bad guards, the proof asserts: \"As ∢(v,g,u)>π, any point that sees r and is left of the supporting line of vg must lie in the polygon Pg.\" No derivation is given, and this is not a direct consequence of the angle condition alone, since r is a reflex vertex outside [u,v]. The subsequent replacement of (g',[u',v']) by (g',[a,b]) also needs a formal argument that [a,b] is a single closed chain and that the replacement preserves a guarding set while making the guard good. Since Theorem 5.4 provides the existence of a start point u∈U_P in an optimal solution, this gap affects the correctness of the overall algorithm.","section":"Section 5, Theorem 5.4"},{"comment":"The binary search over edges e assumes monotonicity of the existence of a bad guard: if the shortest path from u to the maximal endpoint of e is not left-turning, then no v∈e admits a bad guard whose chain ends on e. This is asserted without proof. As the query point v moves along an edge, the combinatorial structure of the shortest path can change; it is not immediate that left-turning-ness of the path to the farther endpoint is necessary for all points on that edge. Since the correctness of the binary search depends on this monotonicity, this step needs a rigorous justification.","section":"Section 6.1, Lemma 6.8"}],"minor_comments":[{"comment":"There are several typos: \"F unding\" in the funding statement, \"we we set\" in the proof of Lemma 6.8, and \"per definition\" should be \"by definition\" in Lemma 4.9.","section":"Throughout"},{"comment":"The phrase \"the unique inclusion-wise maximal interval containing x\" should be clarified: uniqueness is not immediate, since a guard c may see multiple maximal boundary intervals containing the same vertex x of a defining edge. If the definition relies on a tie-breaking rule, it should be stated.","section":"Definition 5.1"},{"comment":"The proof says the bit string for neighboring vertices in the arrangement differs by at most two entries. This is true only if the walk between them crosses no other supporting line; the argument should specify that the walk follows edges of the arrangement, not arbitrary lines.","section":"Lemma 6.6"},{"comment":"The proof of the claim |G_u| ≤ k+1 for arbitrary u is compressed into a parenthetical. A short formal exchange argument would improve readability and make the O(k) bound for every greedy run explicit.","section":"Theorem 7.1"}],"recommendation":"major_revision","confidential_remarks":"The architecture of the paper is promising, and the speedup claim would be significant. However, Lemma 4.9 is genuinely load-bearing and, as stated, its proof is not valid for arbitrary left-turning chains; the shortest-path setting may repair it, but the authors need to supply the missing argument. The Theorem 5.4 'only bad guards' case also needs a complete geometric proof. I would encourage a major revision rather than rejection, because the central idea is coherent and the gaps appear to be fillable within the paper's framework. Please also ask the authors to clarify the representation of the precomputed visibility cores and the monotonicity assumption in the binary search."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this paper has a genuinely new structural result and a much better runtime claim, but it has one load-bearing geometric lemma that I think is false as written. The paper is worth engagement, not yet trustworthy.\n\nWhat's new: the O(n^2) candidate start points via the supporting-line arrangement, the good/bad guard split, and the polylog greedy query structure. Compared to the SoCG'25 merged result, this is a real simplification and a factor ~n^3 improvement. The architecture is coherent: exchange argument for greedy optimality, replacement lemmas for good guards are plausible, and the runtime accounting is consistent.\n\nThe soft spot is Lemma 4.9 in Section 4.2. The proof claims that for a left-turning shortest path S_v, the visibility core is just the intersection of the halfplanes of the first and last edges. That is false for left-turning chains in general: a three-edge chain can have a middle edge whose halfplane adds a constraint not implied by the extremes. The proof supplies no polygon-specific reason why the shortest path context restores the equality. The bad-guard branch of the query structure in Lemma 6.8 depends on exactly this. If the equality fails, the computed guard may not actually see the claimed chain, so the greedy algorithm could output a set that doesn't guard the boundary.\n\nThis is a load-bearing flaw, but the paper is not incoherent. The good-guard part seems solid, and the structural start-point discretization does not rely on Lemma 4.9. A fix might be available—maybe using the full set of halfplanes and arguing the extreme intersection is still in the core under the polygon context—but it's not in the paper. The other concerns (Theorem 5.4's angle inference, Proposition 4.3's subchain claim) are secondary and may be resolvable.\n\nCitations look fair, no fitted parameters, no circularity. The self-citations to [5] are for standard observations. The presentation is clear and the proof length is refreshing.\n\nWho it's for: researchers in computational geometry, art gallery problems, and visibility data structures. It deserves a serious referee: the claim is important and the gap is specific enough to be tested. I'd recommend sending to peer review, and a careful referee should focus on Lemma 4.9.","headline":"A strong structural result with a load-bearing geometric lemma that is false as written; worth a careful referee.","tokens_in":13803,"tokens_out":3236,"would_cite":false,"duration_ms":32903,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A greedy algorithm starting from one of O(n²) carefully chosen boundary points finds an optimal contiguous guard set in O(k n² log² n) time.","keywords":["contiguous art gallery","simple polygon","visibility core","supporting-line arrangement","greedy algorithm","shortest paths","candidate set","computational geometry"],"falsifier":"Take a simple polygon and a bad guard whose shortest path from v to u is a convex left-turning chain with three or more edges; compute the visibility core P_E of the boundary chain and intersect the supporting line of the last edge with it. Compare the maximal chain seen by the intersection point with the true visibility polygon of that point. If the point fails to see any part of [u,v] that the halfplane argument claims, then Lemma 4.9's reduction is false for that instance.","tokens_in":12662,"feed_emoji":"🖼️","tokens_out":8670,"duration_ms":96675,"temperature":0.7,"pith_summary":"This paper gives a polynomial-time algorithm for the contiguous art gallery problem: place the fewest guards in a simple polygon so that each guard is assigned one contiguous boundary interval it can see, and the intervals cover the boundary. The authors prove that an optimal solution can always be found by a greedy procedure if it starts at one of O(n²) candidate boundary points, and they build a data structure that answers each greedy step in O(log² n). The result is an O(k n² log² n)-time, O(n²)-space algorithm, improving on the previous best O(k n⁵ log n) polynomial bound. If the structural theorem holds, the problem has a simple explanation: all hard choices collapse to intersections of supporting lines of polygon edges.","feed_headline":"Greedy from O(n²) starts guards polygons in near-quadratic time","feed_subtitle":"A structural theorem trims all possible guard starts to O(n²), and each greedy step takes only O(log² n).","key_machinery":"The central objects are the visibility core P_E and the arrangement C_P of supporting lines of polygon edges. The visibility core of a set of boundary edges is the intersection of the halfplanes left of their directed supporting lines; a point guards a chain exactly when it lies in the core of the edges the chain crosses. The arrangement's vertices—intersections of two supporting lines—provide the O(n²) candidate guard positions, and the candidate start set U_P comes from maximal visible chains through the defining edges of these vertices. The good/bad guard split is the crucial dichotomy: a guard is good unless the open chain contains a polygon vertex, the guard is not an endpoint, the view","core_discovery":"The paper establishes that the contiguous art gallery problem can be solved in O(k n² log² n) time. Its central structural theorem shows that, for any optimal solution using more than one guard, there is an equal-size optimal solution in which at least one guard's interval starts at a point in a precomputed set U_P of O(n²) boundary points. From such a start, the greedy rule—take the farthest boundary point v such that some guard sees the whole interval [u, v], then repeat from v—produces an optimal solution. The paper additionally proves a query data structure: for any requested start u, the maximal guardable interval from u can be returned in O(log² n) time, with a witness guard. Together","pith_inferences":["The good/bad split may generalize to other boundary-coverage variants: whenever a single guard's visible region is described by a convex visibility core, arrangement vertices can serve as finite candidate sets, potentially yielding polynomial algorithms elsewhere.","If the bad-guard simplification in Lemma 4.9 is ever replaced by an exact visibility query, the rest of the pipeline—O(n²) candidate starts, the greedy proof, and the polylogarithmic query structure—should carry over unchanged.","One could try to shrink U_P further by keeping only arrangement vertices whose two defining edges are both intersected by the maximal chain, which would sharpen the O(n²) factor without changing the method."],"forward_implications":["If the structural theorem is correct, the optimum can be computed by running the greedy maximal-interval rule from every candidate start in U_P and keeping the best output; no backtracking or iterative restart is needed.","The running time is O(k n² log² n) using O(n²) space, a large asymptotic improvement over the previous O(k n⁵ log n) polynomial bound.","Every greedy run returns at most k+1 guards, and the run starting from the guaranteed candidate returns exactly k guards.","The query data structure returns a witness guard along with the maximal chain, so the algorithm outputs an explicit set of contiguous guards, not just a count."],"supporting_citations":[{"why":"The merged prior work establishing that the contiguous art gallery problem is polynomially solvable and giving the O(k n^5 log n) bound; the new algorithm's runtime and candidate-set approach are measured against it.","marker":"[3]"},{"why":"The greedy procedure of taking the maximal visible interval from a start point, which yields at most k+1 guards for an arbitrary start, is the algorithmic template this paper sharpens by using U_P.","marker":"[10]"},{"why":"Supplies the shortest path queries in a simple polygon used to compute the convex shortest path and its first and last supporting lines for a candidate guard.","marker":"[6]"},{"why":"Supplies the ray-shooting primitive used to locate the endpoints u and v of the maximal visible chain from a guard.","marker":"[8]"},{"why":"Supplies the fact that when a guard sees both endpoints and the viewing angle exceeds π, the shortest path between the endpoints is a convex left-turning chain; this drives the bad-guard analysis.","marker":"[7]"}],"fun_headline_variants":["Near-quadratic algorithm for contiguous art gallery","Simpler and faster: art gallery guards in O(n² log² n)","Structural theorem trims guard starts to O(n²)","Greedy with O(n²) starts solves art gallery faster","Guards cover boundary in near-quadratic time"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The load-bearing premise is Lemma 4.9: for a bad guard, the visibility core of the convex shortest-path chain is completely described by the halfplanes left of its first and last edges, so the middle edges never further restrict visibility. If a middle edge can cut the core, the data structure's bad-guard query may certify a chain that the returned guard does not actually see.","fun_headline_variants_meta":{"raw":{"variants":["Near-quadratic algorithm for contiguous art gallery","Simpler and faster: art gallery guards in O(n² log² n)","Structural theorem trims guard starts to O(n²)","Greedy with O(n²) starts solves art gallery faster","Guards cover boundary in near-quadratic time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000865,"raw_usage":{"total_tokens":3582,"prompt_tokens":734,"completion_tokens":2848,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":478,"completion_tokens_details":{"reasoning_tokens":2775}},"tokens_in":478,"tokens_out":2848,"duration_ms":22217,"temperature":1.0,"reasoning_tokens":2775,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T20:52:04.981191+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a simple polygon and a bad guard whose shortest path from v to u is a convex left-turning chain with three or more edges; compute the visibility core P_E of the boundary chain and intersect the supporting line of the last edge with it. Compare the maximal chain seen by the intersection point with the true visibility polygon of that point. If the point fails to see any part of [u,v] that the halfplane argument claims, then Lemma 4.9's reduction is false for that instance.","supporting_citations":[{"cited_title":"A pedestrian approach to ray shooting: shoot a ray, take a walk","cited_arxiv_id":null,"evidence_quote":"Supplies the ray-shooting primitive used to locate the endpoints u and v of the maximal visible chain from a guard."},{"cited_title":"Linear time algorithms for visibility and shortest path problems inside simple polygons","cited_arxiv_id":null,"evidence_quote":"Supplies the fact that when a guard sees both endpoints and the viewing angle exceeds π, the shortest path between the endpoints is a convex left-turning chain; this drives the bad-guard analysis."}],"review_version":1}