Online Algorithms For Evacuating By Groups From The Boundary Unknown Affected Area

The online searching algorithm study of evacuating by groups from the boundary unknown affected area is a theoretical issue abstracted from some practical application problems.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 evacuation problem that the number of groups is n(n?2).To start with,the related basic knowledge of computational geometry involved in this paper are discussed,such as judging whether a point is on the segment,determining whether a point in a polygon,computing the competitive ratio.We make an introduction of the '"doubling strategy" of liner search problem.the equiangular evacuation tactic and the semicircle evacuation strategy of single-point problem by one group in detail,and point out the lack of them.The next,by adopting the idea of semicircle strategy,we put forward the semicircle strategy for two groups on this basis,and apply them to the the number of groups is n(n?3),designed the corresponding fan-shaped evacuation strategy.We analyzed the competitive ratio for every strategy.Once more,we prove that a number of evacuees for n(n?2)semicircle evacuation strategy could solve the evacuation problem for concave zone boundary,and carries on the detailed competitive ratio analysis in concave polygon.Lastly,we encode the semicircle evacuation strategy and the fan-shaped evacuation strategy.We construct the experimental data for verifying the feasibility and effectiveness of the algorithm.