Approximate Algorithms for Touring a Sequence of Polygons

Abstract

Given two points p and q and a nite number of simple poly- gons in a plane. The basic version of a touring-a-sequence-of-polygons problem (in brief: a touring polygons problem, TPP) is how to nd a shortest path such that it starts at p, then it visits these polygons in the given order, and nally it ends at q. This paper describes approximate algorithms for di erent versions of touring polygons problems. Among its important results it provides, for example, an answer to the previ- ously 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 nds an approximate so- lution to the unconstrained touring polygons problem which is known to be NP-hard.