Fast computation of shortest watchman routes in simple polygons

摘要

The watchman route problem deals with finding a shortest route in a simple polygon of n vertices such that each point in the interior of the polygon can be seen from at least one point along the route. In this paper, we show that the shortest watchman route in a simple polygon is unique, except for very special cases where there is an infinite number of shortest routes of equal length, and present an O(n~5) time solution to the watchman route problem. Our result improves upon the previous O(n~6) time bound.