Where to Build a Door

A room is a simple polygon with a prespecified point, called the door, on its boundary. Search starts at the door, and must detect all intruders that may be in the room, while making sure that no intruder escapes through the door during the search. Depending on where the door is placed, the intruders may be able to avoid detection. We present an efficient algorithm that can determine all the intervals on the boundary where the door should be placed in order for the polygon to be searchable by two guards on the boundary who keep mutual visibility, or a single searcher with a flashlight. Our algorithm works in O(n log n) time, where n is the number of vertices of the given polygon