Approximate Algorithms for Touring a Sequence of Polygons
Fajie Li, Reinhard Klette · 2008
Abstract. Given two points p and q and a finite number of simple polygons in a plane. The basic version of a touring-a-sequence-of-polygons problem (in brief: a touring polygons problem, TPP) is how to find a shortest path such that it starts at p, then it visits these polygons in the given order, and finally it ends at q. This paper describes approximate algorithms for different versions of touring polygons problems. Among its important results it provides, for example, an answer to the previously open problem “What is the complexity of the touring polygons problem for pairwise disjoint nonconvex simple polygons? ” by providing a κ(ε)-linear approximate algorithm for solving this problem, with κ(ε) = (L0 − L1)/ε where L0 is the length of the initial path and L is the true (i.e., optimum) path length. As a further example, this paper finds an approximate solution to the unconstrained touring polygons problem which is known to be NP-hard.