Approximating a Shortest Watchman Route
Bengt J. Nilsson · Fundamenta Informaticae · 2001
We present a fast algorithm for computing a watchman route in a simple polygon that is at most a constant factor longer than the shortest watchman route. The algorithm runs in O(n log n) time as compared to the best known algorithm that computes a shortest watchman route which runs in O(n^6) time.