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

Shun LYU, Bo JIANG

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.

Keywords


Computational geometry, Touring polygons problem, Approximate algorithm, Simple polygon, Ratio


DOI
10.12783/dtcse/cmsam2017/16410

Full Text:

PDF

Refbacks

  • There are currently no refbacks.