Given a simple polygon in the plane with two distinguished vertices, s and g ,i s it possible for two guards to simultaneously walk along the two boundary chains from s to g in such a way that they are always mutually visible? We decide this question in time O(n logn) and in linear space, where n is the number of edges of the polygon. Moreover, we compute a walk of minimum length within time O(n logn +k), where k is the size of the output, and we prove that this is optimal.
['Christian Icking', 'Rolf Klein']
The two guards problem