{"id":"a0d25886-37ab-4de2-ba93-bc9523a44636","arxiv_id":"2412.15053","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Contiguous boundary guarding of a simple polygon can be solved optimally in polynomial time, and the tight worst-case guard number is about n/2 for an n-corner polygon.","lead":"This paper introduces a new art gallery variant: a minimum set of guards must watch the boundary of a simple polygon, with each guard covering one continuous stretch of wall. It proves the problem can be solved exactly in polynomial time, and gives the exact worst-case number of guards needed for any polygon with a given number of corners.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the conditional verdict stands, with Lemma 6 remaining the clear fragile premise but no concrete flaw found in the argument.","rationale":"The reader identified Lemma 6 as the weakest assumption, and I agree that this is the correct focus: the exact polynomial-time algorithm reduces to Lemma 6, and the proof of Lemma 6 is long, partly compressed, and not machine-checked. I stress-tested the main components of that proof. The compactness of the lexicographic maximum is not written out, but the space of optimal solutions with fixed guard count and assigned intervals is closed, so the maximum should exist. The movement argument is sequential and each step preserves earlier intersections; the claims about entering Q are backed by the structural lemmas. The OPT=2 and OPT>=3 cases are geometrically intricate, but I could not identify a concrete missing case or a counterexample to the stated local claims. The combinatorial bound and the greedy approximation argument appear internally consistent. Since I cannot point to a specific error, and the reader's conditional verdict already accounts for the residual risk in Lemma 6, I do not recommend changing the verdict. A full formalization of Section 6 would be the natural next step and would either confirm the proof or expose the precise step that fails.","tokens_in":17512,"tokens_out":34253,"duration_ms":228025,"concrete_test":"Re-formalize the choice of Gamma* in Section 6 by proving that the set of optimal solutions in which every guard has maximal coverage is compact under the lexicographic angle order, and then verify the local coverage-preservation claims in the OPT >= 3 case with a concrete 3-guard configuration. In particular, compute the regions A_i, B_i, K_i as defined in Section 6 and directly check the assertion that g_{i+1} cannot lie in A_i because otherwise g_i and g_{i+1} would cover the entire polygon. If this assertion fails for any simple polygon, Lemma 6 collapses; if it holds and the compactness argument goes through, the proof is sound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that contiguous boundary guarding is solvable in polynomial time, via the exact algorithm whose correctness rests on Lemma 6 (some optimal solution has a guard in the candidate set Q) and on Corollary 1 (greedy is optimal from a doubly-covered boundary point). Lemma 6 is genuinely the load-bearing step: its proof selects a lexicographically maximal optimal solution among those with maximal per-guard coverage, then moves guards along edge-extensions to make consecutive coverages meet at points. I examined the least explicit parts of that proof. The sequential movement order in Section 6 does set each intersection after it is created, so later moves do not disturb earlier settled intersections. The assertions that a moving guard cannot cross a new extension without entering Q are supported by Lemmas 8 and 9: a guard on two edge-extensions, or on a vertex-extension while already on an edge-extension, is in Q. The existence of the lexicographically maximal solution is not explicitly proved, but the relevant configuration space is compact once assigned intervals are included, so this is a presentation gap rather than a demonstrated error. I also checked the greedy argument in Theorem 2 and found no flaw that would survive even if Lemma 6 holds. I therefore report no significant objection. The reader's conditional verdict is the appropriate assessment: the paper is internally consistent as far as I can determine, but the complexity and length of the Section 6 proof mean that an independent formal check would be valuable before full acceptance.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the contiguous boundary guarding problem, in which guards must be placed in a simple polygon so that each guard is assigned a contiguous portion of the polygon boundary. The authors prove a tight combinatorial bound of floor((n-2)/2) guards for n-vertex polygons, give a simple greedy algorithm that uses at most OPT+1 guards, and present a polynomial-time exact algorithm. The exact algorithm works by constructing a polynomial-size candidate guard set Q and a set S of boundary starting points, then running the greedy algorithm from each starting point in S. Correctness of the exact algorithm rests on Lemma 6, which asserts that some optimal solution has a guard at a point of Q; the proof of Lemma 6 occupies most of Section 6 and is a long contradiction argument involving lexicographically maximal optimal solutions and continuous movements of guards along edge-extensions.","tokens_in":17775,"tokens_out":7823,"duration_ms":63827,"significance":"If correct, the main theorem is a significant result: the contiguous boundary guarding problem appears to be the first nontrivial boundary guarding variant that is solvable exactly in polynomial time, in contrast to standard point-guard or boundary-guard problems that are NP-hard and even ∃R-complete. The tight combinatorial bound is clean, and the OPT+1 greedy algorithm is simple and elegant. The candidate-set approach is appealing and could be reusable. The paper does not include code or machine-checked proofs, but the arguments are deductive and the external dependencies (visibility polygon computation, the cited lemma from Ghosh) are standard. The main weakness is that the proof of Lemma 6 is lengthy and partly compressed; several load-bearing geometric claims are asserted without full justification. No concrete error was found, but the proof needs substantial elaboration before the paper can be accepted.","major_comments":[{"comment":"The choice of Γ* as a maximal element of G with respect to the lexicographic order on angle sequences is not justified. The set G of optimal guard sets with maximal coverages is not obviously compact, and the text does not prove that a maximal element of this order exists. Since every subsequent argument in Section 6 is about Γ*, the proof of Lemma 6 depends on this existence. The authors should add a compactness or continuity argument, or explicitly construct Γ*, before the contradiction proof can be considered complete.","section":"Section 6, first paragraph after the overview"},{"comment":"The movement argument for constructing Γ is stated too tersely. In particular, the claims that during the movement 'gi cannot reach e(gi) or the boundary of P', 'gi cannot lie on a new edge-extension or vertex-extension', and 'the angle at w(gi) remains at least π because both bounding reflex vertices remain on the same side of the extension of e(gi)' are all asserted without proof. What is needed is a demonstration that the movement can always be continued until the desired intersection ∂(gi) ∩ ∂(gi+1) becomes a point, and that during this movement no point of the boundary that was previously covered becomes uncovered. As written, these steps are not checkable in detail, and they are load-bearing for the construction of Γ.","section":"Section 6, paragraph starting 'By Lemma 12 for every gi ∈ Γ* ...'"},{"comment":"The inclusions 'The coverage ∂(gi+1) of gi+1 also lies in Ki because its first endpoint is xi and its last endpoint cannot go beyond ri' and 'This implies that Ki+1 is a subset of Ki' are not justified. These inclusions are essential for concluding that gm lies in K1 and hence that z'1 cannot be covered, which yields the final contradiction. The authors should provide a rigorous geometric argument for both inclusions, or restructure the proof to avoid them. As it stands, this part of the proof is too compressed to verify.","section":"Section 6, Case 2 (OPT ≥ 3), Figure 14 and surrounding text"},{"comment":"The proof of Lemma 3, that the covering region C(P,δ) of a polygonal path is a simple polygon, is a sketch rather than a complete proof. In the case where q∉Cp and p∉Cq, the text asserts that a boundary ray of Cp and a boundary ray of Cq intersect at a point c, but it does not handle degenerate configurations in which the rays are parallel or collinear, and the claim that c is in C is not fully proved. Since Lemma 3 underlies the polynomial-time computation of covering regions used by the greedy algorithm, its proof should be completed or the lemma should be stated as a direct consequence of the cited results [24,25] with a precise reference.","section":"Section 3, Lemma 3"}],"minor_comments":[{"comment":"The sentence 'The chains are placed close to each other such that the midpoints of no three consecutive edges on a chain are visible from the same point in the polygon' is ambiguous; it should specify which points are 'consecutive midpoints' and clarify how the placement achieves the claimed visibility property.","section":"Section 2, lower bound construction"},{"comment":"In the first case of the proof, the sentence 'By our choice of m and pm−1, the point p∗1 appears on or after pm−2, because otherwise p′1 would be in ∂(pm−2,pm−1)' is difficult to follow and should be expanded or rephrased for clarity.","section":"Section 4, proof of Theorem 2"},{"comment":"The statement that F(q) consists of intersections of ∂ with rays from q through reflex vertices relies on the maximality of ∂(g), which is assumed without loss of generality. It would help to state explicitly that maximality is assumed in the optimal solution under consideration and that this assumption is preserved by the construction of Q.","section":"Section 5, definition of F(q)"},{"comment":"The notation in the OPT=2 and OPT≥3 cases, such as w1, w2, A_i, B_i, and K_i, is introduced in the text but would be easier to follow if the figures were referenced more explicitly and if the definitions were repeated in the captions.","section":"Section 6, Figures 13 and 14"}],"recommendation":"major_revision","confidential_remarks":"The paper is well within the scope of a computational geometry journal and presents an interesting and likely correct contribution. The main risk is the length and opacity of the proof of Lemma 6; I would encourage the editor to require a revision that expands this proof substantially, even if it increases the page count. No concerns about attribution or overlap were identified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is one of the few nontrivial art-gallery variants that is exactly solvable in polynomial time, and my reading says it is probably correct. It deserves a serious referee.\n\nWhat is actually new: the contiguous boundary guarding problem itself, the tight floor((n-2)/2) bound, the greedy OPT+1 algorithm, and the exact polynomial algorithm. The greedy analysis is a clean circular-arc-cover argument, and the combinatorial bound's proof via the dual tree is neat. The authors are also honest that the exact algorithm's correctness proof is involved; they do not hide that.\n\nThe load-bearing step is Lemma 6: some optimal solution has a guard in the candidate set Q. The proof in Section 6 is long and partly compressed. Lemma 3's coverage-region polygon claim is backed by an external citation, and the moving-guard arguments in Section 6 rely on diagrams for local coverage preservation. The compactness needed for the lexicographically maximal solution is asserted rather than proved. The stress-test note checked the least explicit parts and found no concrete error: the sequential movement order sets each intersection after it is created, and Lemmas 8 and 9 support the claim that a moving guard cannot cross a new extension without entering Q. So the gaps are presentation-level, not load-bearing flaws that I can name.\n\nMy own check of the greedy algorithm and the combinatorial bound turned up nothing wrong. There is no fitting or invented data; the paper is a deductive proof from visibility definitions, and the citation pattern looks appropriate.\n\nSoft spots in proportion: Lemma 6 deserves a careful read by a reviewer with time. Some claims like \"the movement cannot make the intersection empty\" are easier to accept with a figure but would benefit from a more formal write-up. The running time is high, O(n^6 log n), but the goal is membership in P, so that is acceptable.\n\nWho this is for: computational geometers working on art galleries and guarding, and anyone interested in which polygon problems become tractable under contiguity constraints. I would cite it, and I would bring it to a reading group as a good example of a modern art-gallery structural proof.\n\nRecommendation: send it to peer review. The central argument looks sound to me, and the reader's conditional verdict is about right: accept if the reviewers verify Lemma 6.","headline":"A genuinely new poly-time art-gallery variant; the exact algorithm is believable but rests on a long structural lemma that needs careful referee scrutiny.","tokens_in":18303,"tokens_out":2081,"would_cite":true,"duration_ms":18408,"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":"Requiring each guard to cover one contiguous boundary arc yields an exact polynomial-time algorithm.","keywords":["contiguous boundary guarding","simple polygon","art gallery problem","visibility polygon","greedy algorithm","polynomial-time exact algorithm","combinatorial guard bound"],"falsifier":"Enumerate all optimal contiguous guardings for all simple polygons up to a small vertex count using exact arithmetic, and check whether every optimal set contains a guard from the paper's candidate set Q; a single polygon whose optimal sets all avoid Q would refute Lemma 6 and with it the exact algorithm.","tokens_in":17362,"feed_emoji":"🛡️","tokens_out":10356,"duration_ms":80427,"temperature":0.7,"pith_summary":"Contiguous boundary guarding asks for the fewest guards inside a simple polygon such that the whole boundary is covered and each guard is assigned one contiguous arc of it. The paper's central result is that this constrained version can be solved exactly in polynomial time, even though the same guarding problem without the contiguity requirement is NP-hard. The argument combines a greedy sweep that is always within one guard of optimal with a structural lemma that produces a polynomial-size list of starting points from which the greedy sweep is exact. The paper also proves that any n-vertex polygon can be guarded with at most $\\lfloor (n-2)/2 \\rfloor$ guards and that this bound is tight.","feed_headline":"Contiguous guard rule makes boundary guarding polynomial","feed_subtitle":"Exact algorithm runs in polynomial time; the worst-case bound of about one guard per two vertices is tight.","key_machinery":"The load-bearing object is the finite candidate set $Q$: all polygon vertices, all points where an edge-extension or vertex-extension hits the boundary, all intersection points of two edge-extensions, and all intersection points of an edge-extension with a vertex-extension, where an extension is a segment from a reflex vertex along an incident edge or between two mutually visible reflex vertices, extended until it hits the boundary. $Q$ has $O(n^3)$ points, and Lemma 6 asserts that some optimal solution has a guard at a point of $Q$. From each $q \\in Q$, the algorithm computes all possible first endpoints of the boundary arc a guard at $q$ could cover, producing the starting-point set $S$ of size $O(n^4)$; by Corollary 1 the greedy sweep from a double-covered starting point is exact. Lemma 6's proof is a contradiction argument: choose a lexicographically maximal optimal solution, show every guard has covering angle at least $\\pi$ and lies on exactly one edge-extension, move consecutive guards so their assigned arcs meet in single points, and conclude that either a guard lands in $Q$ or the boundary cannot be fully covered.","core_discovery":"The paper establishes that the contiguous boundary guarding problem has a polynomial-time exact algorithm. The construction is explicit: build a polynomial-size candidate set Q of guard locations, derive from Q a polynomial-size set S of boundary points that are covered by two guards in some optimal solution, and run the greedy sweep from every point of S, keeping the smallest resulting guard set. The same proof yields the tight combinatorial bound $\\lfloor (n-2)/2 \\rfloor$ for every n-vertex simple polygon. The point of the result is contrast: without contiguity, guarding the boundary of a polygon is a hard optimization problem, so the single-interval assignment is what makes the problem tractable.","pith_inferences":["Beyond the paper: the candidate-set construction is built entirely from single-arc visibility, so a natural testable conjecture is that the same approach extends to guards allowed a fixed number k of boundary intervals, with Q growing polynomially in n for each fixed k.","Beyond the paper: the contrast with the hard ordinary boundary-guarding problem suggests that the number of boundary components one guard may cover is the main source of hardness; if so, allowing k components should interpolate between polynomial and hard as k grows.","Beyond the paper: the OPT+1 greedy sweep, which is fast from a single start, could serve as a practical near-optimal rule for camera systems whose field of view is fixed and cannot rotate, with the exact algorithm available as a certifying check for small instances.","Beyond the paper: the structural proof is written for simple polygons, and it is an open question whether polygons with holes preserve Lemma 6; holes introduce additional reflex chains that the single-extension movement argument does not directly handle."],"forward_implications":["The decision version of contiguous boundary guarding is in P, so optimal guard counts can be computed exactly rather than approximated.","A greedy sweep from an arbitrary boundary point returns a guard set of size at most $\\mathrm{OPT}+1$, and it is exactly $\\mathrm{OPT}$ whenever the starting point is covered by two guards in some optimal solution.","Every simple polygon with n vertices admits a contiguous boundary guarding with at most $\\lfloor (n-2)/2 \\rfloor$ guards, and some polygons require exactly that many.","The exact algorithm runs in $O(n^6 \\log n)$ time, and the paper notes that this bound can likely be improved by using faster visibility-region updates."],"supporting_citations":[{"why":"Supplies the greedy coverage method that the paper adapts to the contiguous boundary case.","marker":"[2]"},{"why":"Provides covering-region ideas underlying Lemmas 2 and 3, which compute the set of points seeing an entire boundary chain.","marker":"[24]"},{"why":"Gives the linear-time visibility-polygon primitive used throughout the greedy and exact algorithms.","marker":"[34]"},{"why":"Supplies polygon-intersection algorithms used to compute covering regions of boundary chains.","marker":"[18]"},{"why":"Provides the diagonal-cut bound used in the tight combinatorial upper-bound proof.","marker":"[10]"}],"fun_headline_variants":["Contiguous boundary guarding solved exactly in polynomial time","Boundary guarding with contiguous segments is now efficient","Polynomial algorithm for contiguous boundary guard placement","Contiguity makes boundary guarding tractable","No more NP-hardness for contiguous boundary guards"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole exact algorithm rests on Lemma 6, the claim that among all optimal guard sets there is one with a guard at a point of the finite candidate set Q; if some polygon had an optimal solution whose guards all avoid Q, the starting-point set S would miss the double-covered point and the greedy sweeps would not be guaranteed to find the optimum.","fun_headline_variants_meta":{"raw":{"variants":["Contiguous boundary guarding solved exactly in polynomial time","Boundary guarding with contiguous segments is now efficient","Polynomial algorithm for contiguous boundary guard placement","Contiguity makes boundary guarding tractable","No more NP-hardness for contiguous boundary guards"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000593,"raw_usage":{"total_tokens":2721,"prompt_tokens":828,"completion_tokens":1893,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":444,"completion_tokens_details":{"reasoning_tokens":1824}},"tokens_in":444,"tokens_out":1893,"duration_ms":12094,"temperature":1.0,"reasoning_tokens":1824,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:41:57.047639+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all optimal contiguous guardings for all simple polygons up to a small vertex count using exact arithmetic, and check whether every optimal set contains a guard from the paper's candidate set Q; a single polygon whose optimal sets all avoid Q would refute Lemma 6 and with it the exact algorithm.","supporting_citations":[{"cited_title":"Partitioning a Polygon Into Small Pieces","cited_arxiv_id":"2211.01359","evidence_quote":"Supplies the greedy coverage method that the paper adapts to the contiguous boundary case."},{"cited_title":"Computing the visibility polygon from a convex set and related problems","cited_arxiv_id":null,"evidence_quote":"Provides covering-region ideas underlying Lemmas 2 and 3, which compute the set of points seeing an entire boundary chain."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the linear-time visibility-polygon primitive used throughout the greedy and exact algorithms."},{"cited_title":"Art galleries and mobile guards: Revisiting O’rourke’s proof","cited_arxiv_id":null,"evidence_quote":"Provides the diagonal-cut bound used in the tight combinatorial upper-bound proof."}],"review_version":1}