Optimal schedules for 2-guard room search
Stephen Bahun, Anna Lubiw · 2007
We consider the problem of searching a polygonal room with two guards starting at a specified door point. While maintaining mutual visibility and without crossing the door, the guards must move along the boundary of the room and eventually meet again. We give polynomial time algorithms for finding a search schedule that minimizes the total distance travelled by the guards and for minimizing the time required for the search by solving L1 shortest path problems among curved obstacles in a polygon. 1