de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

#### Searching a polygonal room with one door by a 1-searcher

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44897

Lee,  Jae-Ha
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Lee, J.-H., Park, S.-M., & Chwa, K.-Y. (2000). Searching a polygonal room with one door by a 1-searcher. International Journal of Computational Geometry and Applications, 10(2), 201-220.

The {\em 1-searcher} is a mobile guard whose visibility is limited to a ray emanating from his position, where the direction of the ray can be changed continuously with bounded angular rotation speed. Given a polygonal region $\poly$ with a specified boundary point $d$, is it possible for a 1-searcher to eventually {\em see} a mobile intruder that is arbitrarily faster than the searcher within $\poly$, before the intruder reaches $d$? We decide this question in $O(n\log n)$-time for an $n$-sided polygon. Our main result is a simple characterization of the class of polygons (with a boundary point $d$) that admits such a search strategy. We also present a simple $O(n^2)$-time algorithm for constructing a search schedule, if one exists. Finally, we compare the search capability of a 1-searcher with that of two guards.