Approximate Algorithm For Touring A Sequence Of Disjoint Simple Polygons In The Plane

This paper focus on touring a sequence of pairwise disjoint simple polygons problem.Touring a sequence of pairwise disjoint simple polygons problem is NP hard,therefore,our goal is to compute an approximate path that starts at starting-point,visiting each polygon in order,and ends at ending-point.Touring polygons problem is the theoretical model of several practical applications,such as cutting problem,therefore,how to find an efficient approximate solution on this problem is not only important on theoretical significance,but also on practical values.There are less researches on pairwise disjoint touring polygons problem,in addition,the work about the ratio of approximate path is urgently to be studied as well.In this paper,we introduce some classic problems and fundamental notions associated with touring polygons problem,such as polygons,the relationship between points and segments,ratio and so on.Then,analyze the different situations of local path of touring polygons in details,and how to divide Last Step Shortest Path Map of convex polygons.According the solution of getting the convex hulls of polygons firstly,obtaining the shortest path of touring convex hulls,and updating the odd and the oven polygons order separately in the end,designs the approximate algorithm of touring polygons.After that,analyze all the ways of updating points when tour the order of polygons in details,provide a ratio and prove the ratio of approximate algorithm by mathematics.Eventually,achieve the approximate algorithm by programming and analysis the differences between experiment results and theoretical ratio,verify the correctness and effectiveness of the approximate algorithm as well.