Touring a sequence of disjoint polygons: Complexity and extension

In the Touring Polygons Problem (TPP) there is a start point s, a sequence of simple polygons P = (P-1,..., P-k) and a target point t in the plane. The goal is to obtain a path of minimum possible length that starts from s, visits in order each of the polygons in P and ends at t. This problem was introduced by Dror, Efrat, Lubiw and Mitchell in STOC'03. They proposed a polynomial time algorithm for the problem when the polygons in P are convex and proved its NP-hardness for intersecting and non-convex polygons. They asked as an open problem whether TPP is NP-hard when the polygons are pairwise disjoint. In this paper, we prove that TPP is also NP-hard when the polygons are pairwise disjoint in any L-p norm even if each polygon consists of at most two line segments. This result complements approximation results recently proposed for the touring disjoint polygons problem. As a similar problem, we study the touring objects problem (TOP) and present an efficient polynomial time algorithm for it. This problem is similar to TPP but instead of polygons, we have solid polygonal objects that the tour cannot pass through. (C) 2014 Elsevier B.V. All rights reserved.