Improved upper bounds on the shortest watchman route in simple polygons: Dependence on reflex vertices and triangulation strategies
Lubomír Štěpánek · Annals of Computer Science and Information Systems · 2025
This paper investigates upper bounds on the length of the shortest watchman route in simple polygons using minimal structural information -specifically, the number and placement of reflex vertices -rather than full geometric detail.We show that the set of reflex vertices alone suffices to guarantee full visibility of the polygon: every interior or boundary point is visible from at least one reflex vertex.Moreover, these vertices can always be connected by a polyline within the polygon, enabling a constructive approach to route design.While it is known that the shortest watchman route is bounded above by the perimeter of the polygon, we prove that this bound is tight and cannot be improved in general.However, we identify several important classes of polygons where significantly better bounds are achievable.In particular, for polygons with exactly two reflex vertices, we establish that the shortest watchman route is strictly shorter than half the perimeter.We also introduce a novel triangulation method -successive dual-edge triangulation -in which each triangle is constructed by attaching to existing polygon edges.When such a triangulation is possible, the resulting watchman route has length strictly less than half the perimeter, regardless of the number of sides or reflex vertices.These results are not only theoretical but also constructive, offering efficient route designs when geometric data is available.The approach is particularly well suited to real-world environments such as industrial halls or private courtyards, where structural simplicity often permits route planning without requiring full geometric reconstruction.In such cases, our methods provide a significant and elegant reduction in route length compared to perimeter-based patrolling, making them applicable to scenarios such as autonomous drone navigation and indoor surveillance.