Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
A Linear-Time Algorithm for Finding All Door Locations That Make a Room Searchable
(Extended Abstract)
verfasst von : John Z. Zhang, Tsunehiko Kameda
Erschienen in: Theory and Applications of Models of Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A
room
is a simple polygon with a prespecified point, called the
door
, on its boundary. Search may be conducted by two guards on the boundary who keep mutual visibility at all times, or by a single boundary searcher with a flashlight. Search starts at the door, and must detect any intruder that was in the room at the time the search started, preventing the intruder from escaping through the door. A room may or may not be searchable, depending on where the door is placed or no matter where the door is placed. We want to find all intervals on the boundary where the door can be placed for the resultant room to be searchable. It is known that this problem can be solved in
O
(
n
log
n
) time, if the given polygon has
n
sides. We improve this complexity to
O
(
n
).