pith. sign in

arxiv: 2606.25816 · v1 · pith:4J2N2MTUnew · submitted 2026-06-24 · 💻 cs.CG · cs.DS

Segment Watchman Routes

Anna Br\"otzner , Omrit Filtser , Bengt J. Nilsson , Christian Rieck , Christiane Schmidt This is my paper

Pith reviewed 2026-06-25 18:58 UTC · model grok-4.3

classification 💻 cs.CG cs.DS
keywords segment watchman routesmin-max criterionmin-sum criterionapproximation algorithmNP-hardnesssimple polygonspolygons with holeswatchman routes
0
0 comments X

The pith

Two routes through a polygon can be found in polynomial time such that every point lies on an internal line segment connecting a point from each route, within factor two of optimal under both min-max and min-sum length criteria.

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

The paper defines segment watchman routes as a pair of paths inside a polygon where every point is covered by lying on a straight-line segment joining the two paths. It establishes that computing the shortest such pair under the min-max criterion is weakly NP-hard already for simple polygons without holes. For the min-sum criterion the problem is NP-hard once holes are allowed. The authors supply sufficient conditions that certify when a pair of routes meets the coverage requirement and give a polynomial-time algorithm that returns routes whose total or maximum length is at most twice the optimum in simple polygons. The same algorithmic approach extends directly to any constant number of routes.

Core claim

Segment watchman routes are two curves W1 and W2 inside a polygon P such that for every point p in P there exist points w1 on W1 and w2 on W2 with the entire segment w1w2 contained in P and containing p. The length of the longer route is minimized under the min-max objective; the sum of lengths is minimized under the min-sum objective. Both objectives admit a 2-approximation algorithm running in polynomial time when P is simple; the min-max version is weakly NP-hard even then, while the min-sum version is NP-hard once holes are present.

What carries the argument

Segment watchman routes: a pair of curves inside the polygon that together cover every interior point by an internal connecting segment.

If this is right

  • The coverage property holds for any pair of routes satisfying the supplied sufficient conditions.
  • A single polynomial-time procedure yields 2-approximations for both the longest-route and total-length objectives in simple polygons.
  • The same approximation guarantee carries over to any fixed number k of routes.
  • The min-max problem remains only weakly NP-hard in the absence of holes, while adding holes makes the min-sum version strongly NP-hard.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same coverage idea could be applied to three-dimensional polyhedra if an analogous visibility segment condition is defined.
  • Practical guarding systems might trade the number of routes against total patrol length once the k-route generalization is implemented.
  • Heuristic search methods for polygons with holes could be benchmarked against the hardness result to measure how often they exceed the factor-two guarantee.
  • The sufficient conditions might be turned into a local-search improvement step that starts from any pair of curves and iteratively enforces the segment-coverage property.

Load-bearing premise

Visibility between points on the two routes is realized exactly by straight-line segments that must lie entirely inside the polygon whose boundary is supplied explicitly as input.

What would settle it

A simple polygon on which an exact optimum under the min-max criterion is computed by exhaustive search or integer programming and the ratio between that optimum and the output of the claimed 2-approximation algorithm exceeds two.

read the original abstract

Motivated by applications for robust guarding, we consider a variant of the multiple-watchmen problem that ensures that every point within a polygon $P$ is seen from more than one direction: we search for two routes $W_1,W_2$, such that every point $p\in P$ is contained in a segment $\overline{w_1w_2}\subseteq P$ such that $w_1\in W_1$ and $w_2\in W_2$. We call such routes segment watchman routes. We show that finding the two routes that are optimal with respect to the min-max criterion is weakly NP-hard even in simple polygons, and that finding the routes that are optimal with respect to the min-sum criterion is NP-hard in polygons with holes. Moreover, we present sufficient conditions for routes to be segment watchman routes, and provide a polynomial-time $2$-approximation under both the min-max criterion and the min-sum criterion, both in simple polygons. Finally, we show how to generalize our results for $k$ watchmen.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces segment watchman routes: two routes W1 and W2 in a polygon P such that every point p in P lies on a line segment between a point on W1 and a point on W2 that is entirely contained in P. It proves that optimizing the min-max length criterion is weakly NP-hard even for simple polygons, while min-sum is NP-hard for polygons with holes. The authors give sufficient conditions for routes to qualify as segment watchman routes, a polynomial-time 2-approximation algorithm for both criteria in simple polygons, and a generalization to k watchmen.

Significance. If the hardness proofs and approximation guarantees hold, the work meaningfully extends the watchman-route literature by adding a robustness requirement (every point covered from two directions along a segment). The 2-approximation in simple polygons and the explicit complexity separations between simple polygons and polygons with holes are the central contributions; the k-watchman generalization broadens applicability. The results rest on standard visibility and polygon representations rather than ad-hoc parameters.

major comments (2)
  1. [Abstract / Section on approximation algorithm] The abstract states the 2-approximation result for both criteria in simple polygons, but the manuscript must explicitly identify the section containing the algorithm and its analysis (including the running-time bound and the proof that the output routes satisfy the segment-watchman property). Without that section reference, the claim cannot be verified as load-bearing.
  2. [Hardness section] The weak NP-hardness claim for min-max in simple polygons is stated without a reduction sketch or reference to the specific gadget construction; if the reduction appears only in an appendix, the main text should at least outline why the problem remains weakly NP-hard (as opposed to strongly NP-hard) and cite the relevant theorem number.
minor comments (2)
  1. [Preliminaries] Clarify whether the input polygon is given with explicit vertex coordinates or as an abstract combinatorial structure; this affects the polynomial-time claim for the approximation.
  2. [Final section] The generalization to k watchmen is mentioned only briefly; a short paragraph stating how the 2-approximation extends (or does not extend) would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed review and constructive suggestions. We address each major comment below and will revise the manuscript accordingly to improve clarity and verifiability.

read point-by-point responses

  1. Referee: [Abstract / Section on approximation algorithm] The abstract states the 2-approximation result for both criteria in simple polygons, but the manuscript must explicitly identify the section containing the algorithm and its analysis (including the running-time bound and the proof that the output routes satisfy the segment-watchman property). Without that section reference, the claim cannot be verified as load-bearing.

    Authors: We agree that an explicit cross-reference would strengthen the abstract. The 2-approximation algorithms (for both min-max and min-sum) and their analyses appear in Section 4, which presents the sufficient conditions, the O(n^2 log n) algorithm, the running-time bound, and the proof that the computed routes satisfy the segment-watchman property (Theorem 4.3). We will revise the abstract to append '(see Section 4)' after the approximation claim. This is a straightforward textual addition that does not alter any technical content. revision: yes

  2. Referee: [Hardness section] The weak NP-hardness claim for min-max in simple polygons is stated without a reduction sketch or reference to the specific gadget construction; if the reduction appears only in an appendix, the main text should at least outline why the problem remains weakly NP-hard (as opposed to strongly NP-hard) and cite the relevant theorem number.

    Authors: The reduction establishing weak NP-hardness of min-max segment watchman routes in simple polygons is given in the main text (Section 3), via a polynomial-time reduction from the Partition problem; the gadget construction and correctness argument occupy the body of that section, and the result is stated as Theorem 3.1. Because Partition is weakly NP-hard, the same holds for our problem. We will add one sentence in the introduction (and a short paragraph at the start of Section 3) that explicitly cites Theorem 3.1 and notes that weak NP-hardness follows from the pseudo-polynomial-time solvability of the source problem. No material will be moved from an appendix. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results are standard complexity and approximation proofs

full rationale

The paper establishes weak NP-hardness for min-max segment watchman routes in simple polygons and NP-hardness for min-sum in polygons with holes, plus a polynomial-time 2-approximation for both criteria. These are proven via explicit reductions and algorithmic constructions that rely on standard visibility and polygon geometry arguments, not on fitted parameters, self-definitions, or load-bearing self-citations. The visibility model is the conventional one from the watchman-route literature, and the claims do not reduce to their own inputs by construction. The derivation chain is self-contained against external benchmarks in computational geometry.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract; no explicit free parameters, axioms, or invented entities are stated. Standard polygon visibility assumptions are implicit but not detailed.

pith-pipeline@v0.9.1-grok · 5725 in / 1086 out tokens · 22110 ms · 2026-06-25T18:58:25.690932+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 14 canonical work pages

  1. [1]

    10.1515/jag-2017-0034

    Effect of target color and scanning geometry on terrestrial LiDAR point-cloud noise and plane fitting , author =. Journal of Applied Geodesy , doi = "10.1515/jag-2017-0034", year =

    work page doi:10.1515/jag-2017-0034 2017

  2. [2]

    Nilsson and Christian Rieck and Christiane Schmidt , title =

    Anna Brötzner and Omrit Filtser and Bengt J. Nilsson and Christian Rieck and Christiane Schmidt , title =

  3. [3]

    Nilsson and Christiane Schmidt , title =

    Anna Brötzner and Bengt J. Nilsson and Christiane Schmidt , title =. Scandinavian Symposium on Algorithm Theory (SWAT) , year =. doi:10.4230/LIPICS.SWAT.2026.11

    work page doi:10.4230/lipics.swat.2026.11 2026

  4. [4]

    Ntafos , title =

    Wei-Pang Chin and Simeon C. Ntafos , title =. Symposium on Computational Geometry (SoCG) , year =. doi:10.1145/10515.10518

    work page doi:10.1145/10515.10518

  5. [5]

    Nilsson and Simeon C

    Svante Carlsson and Bengt J. Nilsson and Simeon C. Ntafos , title =. International Journal of Computational Geometry and Applications , volume =. 1993 , pages =. doi:https://doi.org/10.1007/BFb0028276

    work page doi:10.1007/bfb0028276 1993

  6. [6]

    Optimum Watchman Routes , journal =

    Wei. Optimum Watchman Routes , journal =. doi:10.1016/0020-0190(88)90141-X

    work page doi:10.1016/0020-0190(88)90141-x

  7. [7]

    and Mitchell, Joseph S

    Das, Rathish and Filtser, Omrit and Katz, Matthew J. and Mitchell, Joseph S. B. , title =. Symposium on Computational Geometry (SoCG) , pages =. doi:10.4230/LIPIcs.SoCG.2024.47

    work page doi:10.4230/lipics.socg.2024.47 2024

  8. [8]

    Katz and Joseph S

    Rathish Das and Omrit Filtser and Matthew J. Katz and Joseph S. B. Mitchell , title =. Journal of Computational Geometry , volume =. 2024 , doi =

    2024

  9. [9]

    Efrat, Alon and Har-Peled, Sariel and Mitchell, Joseph S. B. , booktitle=. Approximation algorithms for two optimal location problems in sensor networks , year=. doi:10.1109/ICBN.2005.1589677

    work page doi:10.1109/icbn.2005.1589677 2005

  10. [10]

    Fazli, Pooyan and Davoodi, Alireza and Mackworth, Alan K. , doi =. Multi-robot repeated area coverage , volume =. Autonomous Robots , number =

  11. [11]

    M. R. Garey and Ronald L. Graham and David S. Johnson , title =. Symposium on Theory of Computing (STOC) , pages =. 1976 , doi =

    1976

  12. [12]

    M. R. Garey and David S. Johnson , title =

  13. [13]

    Rahmat Ghasemi and Alireza Bagheri and Anna Br. m -. Computational Geometry , volume =. 2026 , doi =

    2026

  14. [14]

    Huynh and Joseph S

    Kien C. Huynh and Joseph S. B. Mitchell and Valentin Polishchuk , title =. Symposium on Algorithms and Data Structures (WADS) , pages =. doi:10.4230/LIPICS.WADS.2025.39

    work page doi:10.4230/lipics.wads.2025.39 2025

  15. [15]

    2017 , pages =

    Discrete Surveillance Tours in Polygonal Domains , author=. 2017 , pages =

    2017

  16. [16]

    Canadian Conference on Computational Geometry (CCCG) , pages=

    Watchman Routes for Multiple Guards , author=. Canadian Conference on Computational Geometry (CCCG) , pages=

  17. [17]

    and Packer, Eli , title=

    Nilsson, Bengt J. and Packer, Eli , title=. Algorithmica , year=. doi:10.1007/s00453-024-01245-0

    work page doi:10.1007/s00453-024-01245-0

  18. [18]

    and Schuierer, Sven , booktitle=

    Nilsson, Bengt J. and Schuierer, Sven , booktitle=. Shortest m -Watchmen Routes for Histograms: The Minmax Case , year=. doi:10.1109/ICCI.1992.227712

    work page doi:10.1109/icci.1992.227712 1992

  19. [19]

    Nilsson and Derick Wood , title=

    Bengt J. Nilsson and Derick Wood , title=. Canadian Conference on Computational Geometry (CCCG) , pages=

  20. [20]

    Papadimitriou , abstract =

    Christos H. Papadimitriou , title =. Theoretical Computer Science , volume =. doi:10.1016/0304-3975(77)90012-3

    work page doi:10.1016/0304-3975(77)90012-3

  21. [21]

    Canadian Conference on Computational Geometry (CCCG) , pages=

    Triangle Guarding , author=. Canadian Conference on Computational Geometry (CCCG) , pages=

  22. [22]

    2011 , doi =

    Scanning geometry: Influencing factor on the quality of terrestrial laser scanning points , journal =. 2011 , doi =

    2011

  23. [23]

    Remote Sensing , VOLUME =

    Tan, Kai and Cheng, Xiaojun , TITLE =. Remote Sensing , VOLUME =. 2016 , NUMBER =. doi:10.3390/rs8030251

    work page doi:10.3390/rs8030251 2016

  24. [24]

    Information Processing Letters , volume =

    Xuehou Tan , title =. Information Processing Letters , volume =. doi:10.1016/S0020-0190(00)00146-0

    work page doi:10.1016/s0020-0190(00)00146-0

  25. [25]

    Theory and Applications of Models of Computation (TAMC) , pages =

    Xuehou Tan and Bo Jiang , title =. Theory and Applications of Models of Computation (TAMC) , pages =. doi:10.1007/978-3-319-55911-7_44

    work page doi:10.1007/978-3-319-55911-7_44