Searching a Polygonal Region by a Boundary Searcher |
| |
Authors: | Xue-Hou Tan |
| |
Affiliation: | (1) School of High-Technology for Human Welfare, Tokai University, 317 Nishino Numazu 410-0395, Japan |
| |
Abstract: | This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually “see” an intruder
that is unpredictable and capable of moving arbitrarily fast. A searcher is called the boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We
present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher. Based on our characterization, the equivalence of the ability of the
searchers having only one flashlight and the one of the searchers having full 360° vision is simply established, and moreover,
an optimal O(n) time and space algorithm for determining the searchability of simple polygons is obtained. We also give an O(n log n + I) time algorithm for generating a search schedule if it exists, where I (<3n
2) is the number of search instructions reported. Our results improve upon the previously known O(n
2) time and space bounds.
Electronic supplementary material The online version of this article (doi: ) contains supplementary material, which is available to authorized users.
Some preliminary results of this paper were presented at IJCCGGT2003 8]. |
| |
Keywords: | computational geometry robotics visibility polygon search problem two-guard problem |
本文献已被 CNKI 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载全文 |
|