%0 Journal Article
%T Searching a Polygonal Region by a Boundary Searcher
%A Xue-Hou Tan
%A <br>Xue-Hou
%A Tan
%J 计算机科学技术学报
%D 2009
%I 
%X 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].
%K computational geometry
%K robotics
%K visibility
%K polygon search problem
%K two-guard problem<br>无毛
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=50E7692D187A55C4BDCDFBEE436A5D81&yid=DE12191FBD62783C&vid=B91E8C6D6FE990DB&iid=38B194292C032A66&sid=42D7028D961473F8&eid=AF0641F74554D706&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=1&reference_num=1