Algorithms For Evacuating From The Boundary Unknown Affected Area

The study of evacuating from the boundary unknown affected area is a theoretical issue abstracted from some practical application problems. We make some assumptions about the evacuation in this paper, and study how the evacuees escape from the affected area as quickly as possible. Our work can provide technical support to solve some practical problems. Therefore, the study of this paper not only has theoretical significance, but also has important practical application value.The main work of this paper is to solve the single-source point problem and the muti-source point problem. The details are as follows. First of all, the related basic knowledge of computational geometry involved in this paper are discussed, such as judging whether a point is on the segment, constructing the convex hull of planar point set. We make an introduction of the competitive ratio and the Graham method in detail. Then, we discuss the single-source point problem and its evacuation strategy. And analyse detailedly the basic principle, the process and the competitive ratio of the equiangular evacuation tactic. On this basis, we put forward the improved equiangular evacuation tactic. We analyse comparatively the characteristics of the single-source point problem and the multi-source point problem. Then, we give an evacuation strategy to solve the the multi-source point problem and a theoretical analysis result of that the the competitive ratio of this strategy is no more than 4(?)2. In order to verify the correctness and validity of the algorithm, we implement the algorithm using the representative test data.The experimental results show that, evacuation strategies for the single-source point problem and the multi-source point problem presented in this paper can solve these two problems effectively. The experimental results are consistent with the results of theoretical analysis. And, the strategies can ensure that all people evacuate out of the affected area safely and quickly. So, the algorithms proposed in this paper are feasible and effective.