{"id":"44b3823a-f012-43a6-a3a0-4ab2494a4ffa","arxiv_id":"2507.01940","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Optimal two-watchman routes in staircase polygons can be computed in O(n^2) time, and m-watchman min-max routes have an additive-error approximation.","lead":"This paper gives a quadratic-time algorithm for finding the shortest pair of patrol routes that together see every point in a staircase-shaped polygon. It also provides an approximation for any number of patrol routes, with error bounded by the polygon's dimensions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"O(n^2) claim in Theorem 2 rests on an unproved monotone-update invariant in Section 3, Step 1; if a reflex vertex can be re-added or re-released during the sweep, the quadratic bound collapses.","rationale":"Reader's weakest assumption matches my reading: the O(n^2) claim is the central contribution (Theorem 2) and it rests entirely on the amortized constant-time update claim. The structural lemmas (1-4) are compressed and would benefit from more detail, but their statements are plausible and the proof sketches give a credible route to correctness; they are not the point where the argument is most likely to break. The runtime claim, by contrast, is not merely under-detailed: it asserts a specific geometric monotonicity (release-once, add-once, right-to-left/left-to-right) without proof. The cited Harel–Tarjan data structure supplies O(1) LCA queries but not the sweep-order invariant. If the invariant fails, the total work can be superlinear per floor vertex, and the 'quadratic time, improving on cubic' headline is unsupported; the trivial cubic algorithm would be the best proven bound. The proposed test directly counts release/add events and therefore settles whether the invariant holds on instances. Since this is precisely the gap the reader flagged and the conditional verdict is the appropriate response, I see no reason to change the verdict.","tokens_in":9053,"tokens_out":12356,"duration_ms":141165,"concrete_test":"Implement Section 3 Step 1: for each floor vertex p_f, sweep the ceiling endpoint p_c through all ceiling vertices, computing the optimal route in the lower subpolygon exactly (Chin–Ntafos per diagonal). Record, per p_f, the reflex vertices on the ceiling that leave the route and on the floor that enter it. Check whether any ceiling vertex is released more than once, any floor vertex added more than once, and whether total updates over all p_f is O(n^2). If either fails on random/adversarial staircase polygons, the monotonicity invariant is false. Analytically: derive the anchor set as a function of p_c and prove it is a monotone queue; a three-point pattern (route uses reflex r for ceiling vertices p_c1 and p_c3 but not p_c2) refutes the invariant.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the amortized-update invariant in Section 3, Step 1 (the paragraph beginning 'Then, for each diagonal in order'). The paper asserts that for a fixed floor vertex p_f, as the ceiling endpoint moves along the ceiling, 'any reflex vertex on the ceiling touched by the route can only be released once per vertex p_f, and they are released from right to left. Similarly, any reflex vertex on the floor can be added as an anchor point only once per vertex p_f, and they get added from left to right. Hence, the number of updates per vertex p_f is at most linear,' and that each update is 'amortized constant time [3].' No proof of the monotonicity is given; the reference [3] (Harel–Tarjan LCA) provides O(1) ancestor queries but does not establish that the route's anchor set changes monotonically. The claim is asymmetric (ceiling releases, floor additions) and does not justify why ceiling additions or floor releases never occur as the diagonal changes. If any reflex vertex is released and later re-added for the same p_f, or if an update requires more than O(1) work to identify, the total can exceed O(n) per floor vertex, destroying the O(n^2) bound of Theorem 2. Since the quadratic time is the paper's main improvement over the trivial cubic algorithm, this unproved invariant is the most load-bearing assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the multiple watchman route problem (m-WRP) in staircase polygons. For two watchmen, it claims an exact O(n^2) algorithm, improving on a trivial cubic algorithm, for both the min-sum and min-max objectives. The algorithm is based on structural lemmas asserting that an optimal pair of routes can be separated by a diagonal between a reflex vertex on the floor and a reflex vertex on the ceiling, and that only certain 'candidate' diagonals need to be considered. For each floor vertex, the algorithm sweeps the ceiling endpoint and updates two single-watchman routes using shortest-path-tree data structures, with the claim that each update takes amortized constant time. For m >= 3 watchmen, the paper shows why the two-watchman approach fails and gives an additive-error approximation for the min-max criterion using E-routes and dynamic programming in O(m n^8) time.","tokens_in":9350,"tokens_out":5029,"duration_ms":53328,"significance":"If the main theorem is correct, this is the first polynomial-time exact algorithm for the two-watchman route problem in a nontrivial polygon class, and the separation-by-diagonal structural result is a useful contribution that may generalize to other rectilinear monotone polygons. The additive-error approximation for m >= 3 watchmen is also interesting, especially because it explicitly avoids the situation where boundary edges are only partially guarded. The paper is clear about what it does not establish: it notes that the m >= 3 case is genuinely different and that the additive-error algorithm cannot be used to solve minimum point guarding. The main weakness is that the O(n^2) runtime and even the correctness of the candidate-diagonal reduction depend on assertions that are not fully proved, in particular the monotone-update invariant in Section 3, Step 1.","major_comments":[{"comment":"The claim that the total number of updates per floor vertex pf is linear rests on an unproved monotonicity invariant. The text asserts that reflex vertices on the ceiling 'can only be released once per vertex pf' and are released from right to left, and that floor vertices are added only once and from left to right, but no geometric argument is given for why these events are monotone or why re-additions/re-releases cannot occur. The cited Harel-Tarjan ancestor data structure [3] gives O(1) queries, not a monotone update schedule. Since this invariant is the only argument that the per-vertex work is O(n) rather than O(n^2), Theorem 2's O(n^2) bound is not established without a proof of this invariant or an alternative amortization argument.","section":"Section 3, Step 1"},{"comment":"The proof that non-candidate diagonals can be discarded is under-specified. The sentence 'There exists a subpolygon induced by a candidate diagonal ... that also has the horizontal line through p'_c as an essential cut' plus 'the watchman route ... remains the same' is asserted without deriving why the essential cuts of P2 coincide or why the lower route is not longer. Since the algorithm enumerates only candidate diagonals, this lemma is load-bearing for exactness; a full case analysis of the essential cuts for p_f p_c and the neighboring candidate diagonal is needed.","section":"Lemma 4"},{"comment":"The shortening argument in Case 4 assumes that the leftmost vertical line ℓ intersecting both routes cuts P into two subpolygons and that w1 intersects ℓ in at most two points ('the points of intersection'). A closed route may cross ℓ many times, and ℓ may pass through reflex vertices or along edges, so the replacement of w1 by its part in P1 plus a single straight segment is not generally defined. The property that an optimal solution can be assumed to have disjoint x-coordinates therefore needs a more careful treatment of multiple intersections and degenerate cuts.","section":"Lemma 1, Case 4"}],"minor_comments":[{"comment":"The phrase 'do not have any common x- and y-coordinate' is ambiguous; it should specify whether the routes avoid common x-coordinates, common y-coordinates, or both.","section":"Section 2, Lemma 1, Property 1"},{"comment":"Referring to dominated extensions as 'essential cuts' after stating that they are not essential is confusing; consider using a separate term such as 'critical cuts'.","section":"Section 2, Notation"},{"comment":"The citation [3] is to Harel-Tarjan LCA; this supports O(1) ancestor queries but not the claimed 'shortest-path-tree data structures' or amortized updates, so either a different citation or an explicit construction is needed.","section":"Section 3, Step 1"},{"comment":"The statement that 'there are at most five essential cuts' and that all combinations of subsegments can be tried in a constant number of linear-time cases is not fully detailed; please specify how the non-rectilinear essential cut is handled in the Chin-Ntafos reduction.","section":"Section 3, Step 2"},{"comment":"The phrase 'albeit having approximation factor one' is misleading for an additive-error algorithm; the approximation guarantee is additive, not multiplicative, and the sentence should be rephrased.","section":"Section 4, Lemma 6"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern from the reader is valid: the main theorem's runtime rests on an unproved amortization claim in Section 3, Step 1, and the proof of Lemma 4 is also under-specified. I recommend major revision rather than rejection because the structural lemmas are plausible and the missing invariant may be provable from the geometry of staircase polygons. The authors should either prove the monotone-update invariant or, if it fails, replace the O(n^2) claim with the best provable bound and state that as the main result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe paper gives the first exact polynomial algorithm for two watchmen in staircase polygons, and a structural reason why three behave differently. The O(n^2) time is the main selling point, but it rests on an amortization claim that is asserted rather than proved. That is the thing to check first.\n\nWhat is genuinely new: Lemma 3's diagonal separation of the two routes, the candidate-diagonal enumeration (Lemma 4), and the E-route construction for m watchmen with additive error. The paper also does the right thing by showing a concrete configuration where the two-watchman splitting fails for m≥3, and by stating that the additive approximation cannot be turned into an exact point-guarding algorithm. Those caveats are honest and they make the contribution easier to evaluate.\n\nThe soft spots are where the proofs compress. The critical one is Section 3, Step 1: the claim that, as the ceiling endpoint of a diagonal moves, ceiling reflex vertices are released only once per floor vertex and floor reflex vertices are added only once. That monotonicity is the entire justification for the O(n^2) bound. The stress-test is right: reference [3] gives O(1) LCA queries, not the invariant, and the text does not prove that releases and additions are one-way. If a reflex vertex can be re-released or re-added, the amortized linear update per floor vertex fails and Theorem 2 is not established. This is not a minor missing detail; it is the load-bearing step between the structural lemmas and the advertised runtime.\n\nThere are also smaller gaps. Lemma 1, Case 4, is compressed: after cutting at the leftmost vertical line ℓ, the replacement route w1' is asserted to see P1 based on Observation 1, but a few sentences of justification are missing. Lemma 3's uniqueness of the separating diagonal is plausible but the proof is sketchy. And the additive error bound in Lemma 6 is derived in a few lines; I did not find a fatal flaw, but it deserves careful checking.\n\nOn balance, the paper is worth serious referee attention. The structural ideas are new and the honesty about limitations is welcome, but the O(n^2) claim cannot be accepted until the amortization invariant has an actual proof. If the invariant fails, the contribution degrades to a cubic algorithm plus an approximation scheme, which is still publishable but much lower impact.\n\nMy take: send it to reviewers with explicit instructions to verify the Section 3 Step 1 monotonicity. I would not desk-reject it; the potential contribution is real.\n\nBest,\n[Name]","headline":"Genuinely new structural decomposition for two watchmen in staircase polygons, but the advertised O(n^2) runtime rests on an unproved amortization invariant that needs a real proof before the main claim can be trusted.","tokens_in":9828,"tokens_out":5149,"would_cite":true,"duration_ms":58390,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","68W25","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"An optimal solution to the two-watchman route problem in staircase polygons can be computed in $O(n^2)$ time, and for three or more watchmen the min-max version admits an approximation with only additive error.","keywords":["watchman route problem","staircase polygons","multiple watchmen","min-sum criterion","min-max criterion","rectilinear polygons","exact algorithm","approximation algorithm"],"falsifier":"Run the sweep on a family of staircase polygons designed so that, for a fixed floor vertex, the same reflex ceiling vertex must enter and leave the optimal route several times as the diagonal endpoint moves clockwise along the ceiling; if such a polygon exists, the amortized-update argument collapses and with it the $O(n^2)$ runtime proof. A more direct check would instrument the algorithm and count updates per floor vertex, looking for any superlinear total across all diagonals.","tokens_in":8889,"feed_emoji":"📐","tokens_out":9066,"duration_ms":93134,"temperature":0.7,"pith_summary":"The paper's central claim is that the two-watchman route problem in staircase polygons, rectilinear polygons monotone in both coordinate directions, is efficiently solvable exactly. It proves that an optimal pair of closed routes can be found in $O(n^2)$ time for both the min-sum and min-max objectives, improving on the trivial $O(n^3)$ enumeration of all possible separating diagonals. The argument rests on a structural theorem: an optimal pair of routes can always be separated by a diagonal between a floor vertex and a ceiling vertex, so the problem splits into two independent one-watchman problems. For $m \\ge 3$ watchmen the same separation fails because boundary edges may be shared piecewise among several watchmen, and the paper instead gives a min-max approximation algorithm whose error is additive, at most $4(h_{\\max}+v_{\\max})$.","feed_headline":"Quadratic-time exact solution for two watchmen in staircase polygons","feed_subtitle":"A diagonal split reduces the problem to one-watchman subproblems, beating the trivial cubic enumeration.","key_machinery":"The load-bearing objects are the essential cuts, extensions of boundary edges at reflex vertices, and the candidate diagonals between floor and ceiling vertices. A diagonal split creates two subpolygons, and the essential cuts determine the shortest single-watchman route in each subpolygon. A sweep over candidate diagonals, ordered clockwise around each floor vertex, lets the algorithm update the two routes in amortized constant time: reflex vertices on the ceiling are released at most once per floor vertex, floor anchor vertices are added at most once, and each release or addition is detected by shortest-path-tree nearest-common-ancestor queries. For $m$ watchmen, the analogous structural object is an E-route, a left elbow and a right elbow connected along the floor and ceiling by shortest paths; the min-max problem is then solved by dynamic programming over partnering elbows.","core_discovery":"On the paper's own terms, the discovery is Theorem 2: an optimal solution to the 2-WRP in staircase polygons can be computed in $O(n^2)$ time, providing a polynomial exact algorithm for two watchmen in this polygon class. The proof establishes that in some optimal solution the two routes have disjoint coordinate extents, visit complementary essential cuts, and are separated by a diagonal between a floor vertex and a ceiling vertex, so seeing the whole polygon reduces to seeing two subpolygons. The algorithm enumerates candidate diagonals in a carefully chosen order; for each split it computes an optimal watchman route in each subpolygon using a linear-time single-watchman algorithm, and a shortest-path-tree data structure updates the routes in amortized constant time as the diagonal endpoint slides along the ceiling. For $m \\ge 3$, the paper shows the separating-diagonal structure breaks and instead defines canonical E-routes, pairs of left and right elbows joined by shortest paths; a dynamic program over elbows yields a min-max solution of length at most $\\mathrm{OPT}+4(h_{\\max}+v_{\\max})$.","pith_inferences":["The tractability boundary for multiple watchmen may be the separation property: any polygon class where optimal two-watchman solutions always admit a separating diagonal may also admit a polynomial 2-WRP algorithm, while classes with entangled route responsibilities are likely hard; this extrapolation is not stated in the paper.","Since the sweep's amortized-constant updates are the only unproved step in the $O(n^2)$ argument, a natural next target is a proof of the release-and-add monotonicity for all staircase polygons, or a counterexample that forces the runtime back to cubic.","The additive bound $4(h_{\\max}+v_{\\max})$ suggests that for polygons with small horizontal and vertical extent relative to the optimal route length, the canonical E-route solution is nearly optimal; one could test whether a refined choice of elbows halves this additive term.","The fact that E-routes always have positive length means the approximation algorithm does not degenerate into point guarding; allowing degenerate zero-length E-routes might connect the min-max approximation to the open minimum point-guarding problem, but this is an extension rather than a paper claim."],"forward_implications":["The 2-WRP in staircase polygons is exactly solvable in $O(n^2)$ time for both min-sum and min-max objectives, so for this class route optimization is no harder than a quadratic scan of the boundary.","Every optimal two-watchman solution in this class can be assumed to be separated by a single diagonal, meaning the two guards' responsibilities do not interleave along the boundary.","The cubic-to-quadratic improvement comes from amortized updates rather than from reducing the number of candidate diagonals, so any future faster algorithm must exploit a different structural shortcut.","For three or more watchmen, diagonal separation no longer holds; an optimal solution may split the floor and ceiling into more than $m$ responsibility zones, so the two-watchman structural shortcut cannot be reused.","For the min-max objective with $m \\ge 3$, a canonical set of E-routes can be computed by dynamic programming in $O(mn^8)$ time, with length at most $\\mathrm{OPT}+4(h_{\\max}+v_{\\max})$, a one-approximation in the additive-error sense."],"supporting_citations":[{"why":"Supplies the linear-time algorithm for an optimal single watchman route in simple rectilinear polygons, called for each subpolygon induced by a candidate diagonal.","marker":"[2]"},{"why":"Supplies the shortest-path-tree nearest-common-ancestor data structure used to keep the sweep updates amortized constant.","marker":"[3]"},{"why":"Supplies the lemma that two watchmen see a simple polygon if they together see its boundary, used in the optimality argument, and gives prior approximation context.","marker":"[5]"},{"why":"Introduces the m-watchmen route problem and gives min-sum algorithms for restricted polygons, setting the problem studied here.","marker":"[1]"},{"why":"Establishes NP-hardness of the two-watchman min-max problem in simple polygons, motivating the restricted staircase class.","marker":"[4]"},{"why":"Provides min-max algorithms for histograms, the closest prior restricted class for multiple watchmen.","marker":"[6]"}],"fun_headline_variants":["Two watchmen in staircase polygons: exact O(n²) routes","Quadratic-time exact routes for two watchmen in staircases","Staircase polygons: exact two-watchman routes in O(n²)","Faster exact watchman routes: two watchmen, quadratic time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The $O(n^2)$ bound for the two-watchman algorithm relies on the unproved claim that, as the diagonal endpoint moves along the ceiling, each reflex ceiling vertex is released only once per floor vertex and each route update costs amortized constant time via the shortest-path-tree structure; if this monotonicity or constant-time query bound fails, the algorithm's worst case may be cubic rather than quadratic.","fun_headline_variants_meta":{"raw":{"variants":["Two watchmen in staircase polygons: exact O(n²) routes","Quadratic-time exact routes for two watchmen in staircases","Staircase polygons: exact two-watchman routes in O(n²)","Faster exact watchman routes: two watchmen, quadratic time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00031,"raw_usage":{"total_tokens":1709,"prompt_tokens":829,"completion_tokens":880,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":445,"completion_tokens_details":{"reasoning_tokens":804}},"tokens_in":445,"tokens_out":880,"duration_ms":8452,"temperature":1.0,"reasoning_tokens":804,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:39:58.317312+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the sweep on a family of staircase polygons designed so that, for a fixed floor vertex, the same reflex ceiling vertex must enter and leave the optimal route several times as the diagonal endpoint moves clockwise along the ceiling; if such a polygon exists, the amortized-update argument collapses and with it the $O(n^2)$ runtime proof. A more direct check would instrument the algorithm and count updates per floor vertex, looking for any superlinear total across all diagonals.","supporting_citations":[{"cited_title":"Chin and S","cited_arxiv_id":null,"evidence_quote":"Supplies the linear-time algorithm for an optimal single watchman route in simple rectilinear polygons, called for each subpolygon induced by a candidate diagonal."},{"cited_title":"Harel and R","cited_arxiv_id":null,"evidence_quote":"Supplies the shortest-path-tree nearest-common-ancestor data structure used to keep the sweep updates amortized constant."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the lemma that two watchmen see a simple polygon if they together see its boundary, used in the optimality argument, and gives prior approximation context."},{"cited_title":"Carlsson, B","cited_arxiv_id":null,"evidence_quote":"Introduces the m-watchmen route problem and gives min-sum algorithms for restricted polygons, setting the problem studied here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of the two-watchman min-max problem in simple polygons, motivating the restricted staircase class."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides min-max algorithms for histograms, the closest prior restricted class for multiple watchmen."}],"review_version":1}