The Research On Min-max Distance Algorithm Of Two Guards In A Scannable Simple Polygon

The two guards problem in a scannable simple polygon is the abstract models of practical application problem, two guards need to always mutually visible during the scanning process under constrain conditions, researching the optimum sweep scheme is not only significant from the theoretical aspect, but also important in practice. Generally speaking, scanning process of the two guards problem in a scannable simple polygon is composed of straight walk pieces and counter walk pieces, this paper focuses on the counter walk.This paper will give a research to the min-max problem of the two guards problems that the maximum visible distance of the two guards is minimized in a scannable simple polygon. First, through to the correlation data analysis and the research, discussed the basic theory of Computational Geometry and the classic art galley problem and the Frechet distance problem and the two guards problem in detail, based on this, analyzes in depth the properties of scannable simple polygon and focuses on the counter walk, and then discusses several possible cases of the atomic counter walk as well as the optimal walk constructed with a number of atomic straight walk and atomic counter walk. Then we give the method of constructing critical segments and atomic counter walks in the counter scanning process and combining the relative theory of atomic straight walks to build up the atomic walk diagram, and apply Dijkstra algorithm to solve the min-max problem and conclude the optimum scheme. By designing data structures, we present an O(n2) time algorithm for solving this problem in the case of counter walk and an O(n2logn) time algorithm for solving this problem in the case of general walk. Then do more detailed analysis for the running result. And then verify the validity of the presented algorithm.