A Unified Framework for Two-guard Walk Problem

摘要

We propose a unified framework to study the walk problem in a polygonal area by two collaborative guards. A walk is conducted by the two mobile guards on the area's boundary. They start at an initial boundary point, move along the boundary, and may possibly meet together again at an ending boundary point. It is required that the two guards maintain their mutual visibility at all times. Depending the geometric properties of the polygonal area, a walk may or may not be possible. In this work, three versions of the problem, namely, general polygon walk, room walk and street walk, are characterized in a unified manner in our framework. One additional merit of our framework is its simplicity. Applications of the walk problem by two guards include military rescue, area exploration, art gallery surveillance, etc.