The two guards problem

Publisher Website
Google Scholar
Abstract
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.

This publication has 0 references indexed in Scilit: