A unified framework for two-guard street walk problems
John Z. Zhang · 2007
Imagine that two robots collaborate to search in a street area, which has an entrance and an exit. At an abstract level, this is the well-known two-guard street walk problem. In essence, given a simple polygonPwith two distinct vertices s andgon its boundary and two guards (robots), the general street walk problem asks whether the two guards can move on the boundary ofPfrom s togin the opposite directions such that they always maintain their mutual visibility. The other variations, i.e., straight street walk, counter street walk, straight counter street walk, have also been studied. In this paper, we propose a simple unified framework for characterizing walkable streets under these variations.