Multiple Watchman Routes in Staircase Polygons

Anna Br\"otzner; Bengt J. Nilsson; Christiane Schmidt

REVIEW 3 major objections 5 minor 8 references

Multiple Watchman Routes in Staircase Polygons

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2507.01940 v1 pith:QZJTX6TV submitted 2025-07-02 cs.CG

Anna Brötzner , Bengt J. Nilsson , Christiane Schmidt This is my paper

classification cs.CG MSC 68U0568W2568Q25

keywords watchmanrouteproblemstaircasepolygonsmultiplewatchmenmin-sumcriterionmin-maxrectilinearexactalgorithmapproximation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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})$.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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})$.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear colleague,

The 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.

What 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.

The 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.

There 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.

On 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.

My 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.

Best, [Name]

Referee Report

3 major / 5 minor

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.

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 (3)

[Section 3, Step 1] 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.
[Lemma 4] 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.
[Lemma 1, Case 4] 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.

minor comments (5)

[Section 2, Lemma 1, Property 1] 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 2, Notation] 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 3, Step 1] 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 3, Step 2] 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 4, Lemma 6] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the 2-WRP algorithm reduces to independent Chin–Ntafos and Harel–Tarjan results, and no fitted value or self-referential definition is renamed as a prediction.

full rationale

The core derivation is self-contained with respect to its target result. The algorithm for two watchmen enumerates candidate diagonals between floor and ceiling vertices and, for each induced subpolygon, invokes the independent linear-time single-watchman algorithm of Chin and Ntafos (Theorem 1) and the Harel–Tarjan shortest-path-tree/LCA data structure for ancestor queries. No parameter is fitted to the computed optimum, no cost is expressed in terms of the target route lengths, and no equation defines its prediction in terms of its input. The approximation bound of Lemma 6 is an additive error in polygon dimensions (hmax, vmax), not in the optimal value, so it cannot be an artifact of fitting. The only noticeable self-citation is Lemma 3.1 of [5] (Nilsson and Packer, with a coauthor overlap), used in Lemma 1's proof to argue that two watchmen see a polygon when its boundary is seen. That lemma is an independent published property of simple polygons, it is not a uniqueness claim, and it does not by itself assert the existence or optimality of the separating diagonal; the rest of Lemma 1's proof does the structural work. The most fragile point in the paper is the assertional amortized-update invariant in Section 3, Step 1, where unreleased/unre-added monotonicity of reflex-vertex updates is assumed and each update is claimed to take amortized constant time via [3]. That is a potential correctness or proof-completeness gap, but it is not circular: the bound is claimed from an external data-structure query model, not from the target theorem. Thus, no circular step reduces the paper's results to their own inputs.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central results depend on prior algorithmic results and geometric visibility observations. No free parameters are fitted to data, and no new physical or combinatorial entities with independent evidence are introduced.

assumptions (4)

standard math Chin-Ntafos theorem: a shortest single watchman route in a simple rectilinear polygon can be found in linear time.
Assumed correct as cited from [2]; used in Step 1 to compute optimal routes in subpolygons.
standard math Harel-Tarjan shortest-path tree data structure supports nearest-common-ancestor queries in amortized constant time.
The paper's amortized update claim in Section 3, Step 1 depends on this data structure and its query complexity.
domain assumption Observation 1 visibility fact: a watchman sees all points whose x-coordinate lies between its leftmost and rightmost coordinates, with the analogous statement for y-coordinates.
Used throughout to argue visibility of subpolygons; intuitively true for x- and y-monotone staircase polygons but not formally proved in detail.
domain assumption For two watchmen, seeing the complete polygon boundary is sufficient to see the whole polygon, as stated in [5].
The splitting arguments in Lemmas 2 and 3 rely on this boundary-visibility criterion from prior work.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Multiple Watchman Routes in Staircase Polygons." pith.science (2026). https://pith.science/paper/QZJTX6TV

@misc{pith2026250701940,
  author       = {Pith},
  title        = {Pith review of: Multiple Watchman Routes in Staircase Polygons},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QZJTX6TV}},
  note         = {Machine review of arXiv:2507.01940}
}

abstract

We consider the watchman route problem for multiple watchmen in staircase polygons, which are rectilinear $x$- and $y$-monotone polygons. For two watchmen, we propose an algorithm to find an optimal solution that takes quadratic time, improving on the cubic time of a trivial solution. For $m \geq 3$ watchmen, we explain where this approach fails, and present an approximation algorithm for the min-max criterion with only an additive error.

Figures

Figures reproduced from arXiv: 2507.01940 by the authors.

**Figure 2.** Optimal solutions for (a) one watchman, (b) two watchmen, (c) three watchmen. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Four possibilities for w1 and w2 to visit the up to four essential cuts. Consider the route w2 ∪ s2, and shorten it by removing the connected part of length ∥s2∥ that starts at hbot to obtain a new route w ′ 2 of the same length as w2. Then we substitute w1 by a vertical segment w ′ 1 of length ∥s2∥ with lowest point q1. The new route w ′ 1 is shorter than w ′ 2 . Moreover, P is seen from (w ′ 1 , w′ 2 ) because the… view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: (a) The candidate diagonals of a reflex vertex [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

**Figure 5.** Figure 5: A left elbow defined by pc and pf , and right elbows defined by p ′ c and p ′ f , p ′′ f , and p ′′′ f (purple). 4 An Approximation Algorithm for Min-Max Multiple Watchman Routes For the general case of m watchmen, we propose an approximation algorithm for the min-max …

**Figure 6.** Figure 6: Transforming an optimal route w (red) into an E-route (orange). The algorithm, albeit having approximation factor one, since the approximation error is additive, will never compute a route of length zero. Hence, it cannot be used to obtain a polynomial time solution to…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages

[3]

Harel and R

D. Harel and R. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338–355, 1984

work page 1984
[1]

Carlsson, B

S. Carlsson, B. J. Nilsson, and S. C. Ntafos. Optimum guard covers and m-watchmen routes for restricted polygons. Int. J. Comput. Geom. Appl., 3(1):85–105, 1993

work page 1993
[2]

Chin and S

W. Chin and S. C. Ntafos. Optimum watchman routes. Inf. Process. Lett., 28(1):39–44, 1988

work page 1988
[4]

J. S. B. Mitchell and E. L. Wynters. Watchman routes for multiple guards. In Proc. 3rd CCCG, volume 9, pages 293–327, 1991

work page 1991
[5]

B. J. Nilsson and E. Packer. Approximation algorithms for the two-watchman route in a simple polygon.Algorithmica, 86(9):2845–2884, Sep 2024

work page 2024
[6]

B. J. Nilsson and S. Schuierer. Shortest m-watchmen routes for histograms: the minmax case. In Proceedings ICCI ‘92: Fourth International Conference on Computing and Information, pages 30–33, 1992

work page 1992
[7]

X. Tan. Fast computation of shortest watchman routes in simple polygons. Information Processing Letters, 77(1):27– 33, 2001

work page 2001
[8]

Tan and B

X. Tan and B. Jiang. Efficient algorithms for touring a sequence of convex polygons and related problems. In T. V. Gopal, G. J¨ ager, and S. Steila, editors,Theory and Applications of Models of Computation - 14th Annual Conference, 2017, Bern, Switzerland, April 20-22, 2017, Proceedings, volume 10185 of LNCS, pages 614–627, 2017. 9

work page 2017

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [3]

Harel and R

D. Harel and R. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338–355, 1984

work page 1984

[2] [1]

Carlsson, B

S. Carlsson, B. J. Nilsson, and S. C. Ntafos. Optimum guard covers and m-watchmen routes for restricted polygons. Int. J. Comput. Geom. Appl., 3(1):85–105, 1993

work page 1993

[3] [2]

Chin and S

W. Chin and S. C. Ntafos. Optimum watchman routes. Inf. Process. Lett., 28(1):39–44, 1988

work page 1988

[4] [4]

J. S. B. Mitchell and E. L. Wynters. Watchman routes for multiple guards. In Proc. 3rd CCCG, volume 9, pages 293–327, 1991

work page 1991

[5] [5]

B. J. Nilsson and E. Packer. Approximation algorithms for the two-watchman route in a simple polygon.Algorithmica, 86(9):2845–2884, Sep 2024

work page 2024

[6] [6]

B. J. Nilsson and S. Schuierer. Shortest m-watchmen routes for histograms: the minmax case. In Proceedings ICCI ‘92: Fourth International Conference on Computing and Information, pages 30–33, 1992

work page 1992

[7] [7]

X. Tan. Fast computation of shortest watchman routes in simple polygons. Information Processing Letters, 77(1):27– 33, 2001

work page 2001

[8] [8]

Tan and B

X. Tan and B. Jiang. Efficient algorithms for touring a sequence of convex polygons and related problems. In T. V. Gopal, G. J¨ ager, and S. Steila, editors,Theory and Applications of Models of Computation - 14th Annual Conference, 2017, Bern, Switzerland, April 20-22, 2017, Proceedings, volume 10185 of LNCS, pages 614–627, 2017. 9

work page 2017