Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Lee, Jae-Ha Park, Sang-Min Chwa, Kyung-Yong dblp dblp dblp
 BibTeX cite key*: Leejh2000a

 Title
 Title*: Searching a polygonal room with one door by a 1-searcher

 Journal
 Journal Title*: International Journal of Computational Geometry and Applications Journal's URL: http://journals.wspc.com.sg/ijcga/ijcga.html Download URL for the article: Language: English

 Publisher
 Publisher's Name: World Scientific Publisher's URL: Publisher's Address: Singapore ISSN: 0218-1959

 Vol, No, pp, Date
 Volume*: 10 Number: 2 Publishing Date: April 2000 Pages*: 201-220 Number of VG Pages: Page Start: Page End: Sequence Number: DOI:

 Note: (LaTeX) Abstract: 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. URL for the Abstract: Categories, Keywords: Computation Geometry, Visibility, Pursuit-evasion, Graph algorithm HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level:

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{Leejh2000a,
AUTHOR = {Lee, Jae-Ha and Park, Sang-Min and Chwa, Kyung-Yong},
TITLE = {Searching a polygonal room with one door by a 1-searcher},
JOURNAL = {International Journal of Computational Geometry and Applications},
PUBLISHER = {World Scientific},
YEAR = {2000},
NUMBER = {2},
VOLUME = {10},
PAGES = {201--220},