2-Approximate Algorithm for Touring a Sequence of Pairwise Disjoint Simple Polygons

Abstract

In this paper, a 2-approximate algorithm is described to answer the previously open problem “What is the complexity of the TPP for disjoint non-convex simple polygons†which is known to NP-hard. We provide a O(kn) approximate algorithm, where k is polygon counts, and n is the number of vertexes of the polygons, to efficiently find a path which is 2 times at most than the shortest path. To solve this problem, we transform all of simple polygons into corresponding convex polygons, then process the shortest path of convex polygons according to the parity of polygons sequence and finally obtain the approximate path of simple polygons.