论文部分内容阅读
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.
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 previously previously known O (n ~ 2) time and space bounds.