Surveillance of a polygonal area by a mobile searcher from the boundary: Searchability testing

摘要

We study the surveillance of a polygonal area by a robot, which is equipped with a flashlight and moves along the polygon boundary. Its aim is to illuminate any intruder who can move faster than the moving flashlight beam, trying to avoid detection. We propose an O(n)-time algorithm for testing if it is possible for such a robot to always detect any intruder in a given polygon, where n is the number of vertices of the given polygon. This improves upon the best previous time complexity of O(n log n).