Abstract
We consider the problem of searching for a moving target with unbounded speed in a dark polygonal region by a searcher. The searcher continuously moves on the polygon boundary and can see only along the rays of the flashlights emanating from his position at a time. We present necessary and sufficient conditions for a polygon of n vertices to be searchable from the boundary. Our two main results are the following:
-
1
We present an O(n log n) time and O(n) space algorithm for testing the searchability of simple polygons. Moreover, a search schedule can be reported in time linear in its size I, if it exists. For the searcher having full 360° vision, I < 2n, and for the searcher having only one flashlight, I < 3 n 2. Our result improves upon the previous O(n 2) time and space solution, given by LaValle et al [5]. Also, the linear bound for the searcher having full 360° vision solves an open problem posed by Suzuki et al [7].
-
2
We show the equivalence of the abilities of the searcher having only one flashlight and the one having full 360° vision. Although the same result has been obtained by Suzuki et al [7], their proof is long and complicated, due to lack of the characterization of boundary search.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Chazelle, B., Guibas, L.J.: Visibility and intersection problems in plane geometry. Disc. Comput. Geom. 4, 551–581 (1989)
Das, G., Heffernan, P.J., Narasimhan, G.: LR-visibility in polygons. Comput. Geom. Theory Appl. 7, 37–57 (1997)
Heffernan, P.J.: An optimal algorithm for the two-guard problem. IJCGA 6, 15–44 (1996)
Icking, C., Klein, R.: The two guards problem. IJCGA 2, 257–285 (1992)
LaValle, S.M., Simov, B., Slutzki, G.: An algorithm for searching a polygonal region with a flashlight. IJCGA 12, 87–113 (2002)
Suzuki, I., Yamashita, M.: Searching for mobile intruders in a polygonal region. SIAM J. Comp. 21, 863–888 (1992)
Suzuki, I., Tazoe, Y., Yamashita, M., Kameda, T.: Searching a polygonal region from the boundary. IJCGA 11, 529–553 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tan, X. (2005). A Characterization of Polygonal Regions Searchable from the Boundary. In: Akiyama, J., Baskoro, E.T., Kano, M. (eds) Combinatorial Geometry and Graph Theory. IJCCGGT 2003. Lecture Notes in Computer Science, vol 3330. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30540-8_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-30540-8_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24401-1
Online ISBN: 978-3-540-30540-8
eBook Packages: Computer ScienceComputer Science (R0)