AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
Xuehou Tan, Tomio Hirata, Yasuyoshi Inagaki · International Journal of Computational Geometry & Applications · 1993
The problem of finding the shortest watchman route in a simple polygon P through a point s on its boundary is considered. A route is a watchman route if every point inside P can be seen from at least one point along the route. We present an incremental algorithm that constructs the shortest watchman route in O(n3) time for a simple polygon with n edges. This improves the previous O(n4) bound.