Research On The Optimal Algorithm For Touring A Sequence Of Disjoint Circles In The Plane

In this paper,we study the optimal algorithm for the shortest path problem of touring a sequence of disjoint circles in the plane,the target is to find a global shortest path starting from the given start point,then touring every circles by order,at last ending at the given target point.This problem is not only a theoretical problem in geometric computing field,but also an abstract model for many practical applications,finding solutions for this problem have both theoretical significance and practical values.Based on the existing solutions to the problem of disjoint segments and polygons in the plane,analysis of geometric features of disjoint circles,this paper put forward to construct the common tangent between adjacent circles,in order to quickly determine the local optimal path,then combine and optimize them to get the global solution.Therefore,this paper explores some classic problems associated with touring circles problems,as well as some basic knowledge such as how to judge the position between point and circles,the common tangent between circle and circle and also the reflection point and perfect reflection,then analysis of the type of access,the calculation method of the local optimal path are given respectively.On this basis,by using the existence and uniqueness of the shortest path of the disjoint circles,technical method for local optimization and combination,this article put forward an algorithm whose time complexity is O(n2)to the problem of disjoint circles in the plane.In order to verify the effectiveness of the algorithm,we design the appropriate data structures and programming to implementation,analysis visualization algorithm operating results.The results show that the algorithm is an optimal solution for solving the problem of touring a sequence of disjoint circles in the plane.