The Research On Min-sum Algorithm Of Two Guards In The Simple Polygon

Two-guard problem is one of the typical problems in Computational Geometry. Its main research topic is as follows. A simple polygon P with an entrance s and an exit t on its boundary is called a corridor. The problem of sweeping corridors with two guards asks the guards to start at the entrance s and force the target out of the region through the exit t. These types of guard problems are motivated by the relations to the well-known Art Gallery and Watchman Route problems. They are devoted to detect an unpredictable, moving target in an n-sided polygon P by a group of mobile guards.This paper will give a further research to min-sum problem of the two-guard model problems that the sum of the distances travelled by the two guards in the sweep is minimized in a simple polygon. The motivation for studying this problem arises from the fact that the cost or energy required by a mobile robot (guard) is an increasing function of the distance it travelled.First, this paper researches some relevant basic knowledge of Computational Geometry. Then introduce the classic guard problems, include Art Gallery, Watchman Route and two-guard problems. Then we study the two basic sweeps:straight sweep and counter sweep, and give respectively several ways of obtaining control shots in straight sweep and counter sweep. Then, we build up rayshooting segement diagram, and apply it to solve min-sum problem. At last, explore an optimum sweep schedule for min-sum problem, and design corresponding data structure and implement the algorithm. Then verify the feasibility and validity of the presented algorithm. For running result do more detailed analysis.