Research On Several Strategies Of Polygon Search

In computational geometry, the polygon search problem is very fundamental. It isthe problem of finding intruders who move unpredictably in a polygonal region by usingone or more mobile searchers (having various levels of vision). In this problem, boththe searcher(s) and the intruders are represented by points that can move continuouslyand freely within a polygonal region, where the latter can move arbitrarily faster than theformer.Polygon search problem which combines with the robot technology is widely usedin many areas, such as navigation, security defense, target detection and tracking, and soon. Therefore, for a given polygon, to determine whether it can be searched by one ormore searchers with various levels of vision, and how to find a more effective search pathis very important.In this paper we consider the polygon search problem by using a boundary 1-searcher, who has a single ?ashlight and is only allowed to move along the boundaryof a simple polygon with n edges. As a special case of the polygon search problem, itattracted much attention of many scholars, and obtained some characterizations and thesearch algorithm, but there are some deficiencies in them. Based on in-depth analysis ofthe research status and the disadvantage of the problem, we conclude our main results asfollows.First, the related concepts of the polygon search problem to be introduced. More-over, the pruned skeleton V diagram can be constructed by using a new method whichcombines the bi-tangent with the visibility (V) diagram of the polygon.Second, for the problem of searching a simple polygonal region with a boundary 1-searcher, the necessary and sufficient conditions for testing the searchablity of polygonsare proposed. It is showed that whether a polygon is searchable by a boundary 1-searchercan be detected in O(n) time and space by using these conditions. The results improvethe previous O(nlogn) time bounds. This is the best result until now. At the same time,some known proving processes are simplified by using the pruned skeleton V diagram.Third, a novel search algorithm is presented, and the performance of it is describedin detail. Meanwhile, we prove that the algorithm can generate a search schedule with thetime complexity O(m), if it exists, where m(< n~2) is the number of search instructions,which is better than the previous O(n log n + I) (I < 3n~2) time algorithm. Moreover, itis showed that the distance traveled by the boundary 1-searcher is the shortest by using our search algorithm, and the maximum distance is less than 2|(?)P|, where |(?)P| is thetotal length of the polygon boundary.