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:








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, Abstract, ©

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},
ADDRESS = {Singapore},
MONTH = {April},
ISBN = {0218-1959},
}


Entry last modified by Uwe Brahm, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Jae Ha Lee
Created
02/21/2001 11:50:01 AM
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Uwe Brahm
Anja Becker
Jae Ha Lee
Edit Dates
04/09/2001 12:22:32 PM
04/04/2001 06:12:31 PM
20.03.2001 17:18:10
21/02/2001 11:50:01