# A Linear-time Algorithm for Orthogonal Watchman Route Problem with Minimum Bends

arXiv: https://arxiv.org/abs/1708.01461 · HTML: https://mlsanity.com/paper/1708.01461/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2017.

## Built on by (most cited first, 2 of 2)

- [Minimizing Turns in Watchman Robot Navigation: Strategies and Solutions](https://mlsanity.com/paper/2308.10090/) (2023)
- [Securing Pathways with Orthogonal Robots](https://mlsanity.com/paper/2308.10093/) (2023)

## Abstract (arXiv)

Given an orthogonal polygon  P  with  n  vertices, the goal of the watchman route problem is finding a path  S  of the minimum length in  P  such that every point of the polygon  P  is visible from at least one of the point of  S . In the other words, in the watchman route problem we must compute a shortest watchman route inside a simple polygon of  n  vertices such that all the points interior to the polygon and on its boundary are visible to at least one point on the route. If route and polygon be orthogonal, it is called orthogonal watchman route problem. One of the targets of this problem is finding the orthogonal path with the minimum number of bends as possible. We present a linear-time algorithm for the orthogonal watchman route problem, in which the given polygon is monotone. Our algorithm can be used also for the problem on simple orthogonal polygons  P  for which the dual graph induced by the vertical decomposition of  P  is a path, which is called path polygon.