Touring Polygons, Parts Cutting, and q-Rectangles

Abstract

Given a sequence of k simple polygons in a plane, a start point p, and a target point q. We approximately compute a shortest path that starts at p, then visits each of the polygons in the specified order, and finally ends at q. So far no solution was known if the polygons are pairwise disjoint and non-convex. By applying a rubberband algorithm, we give an approximative algorithm with time complexity in kappa(epsilon) times O(n), where n is the total number of vertices of the given polygons, and function kappa(epsilon) is as follows: kappa(epsilon) = (L_0 - L)/epsilon, where L_0 is the length of the initial path, and L is the true (i.e., optimum) path length. The given rubberband algorithm can also be applied to solve approximately three NP-complete or NP-hard 3D Euclidean shortest path (ESP) problems in time kappa(epsilon) times O(k), where k is the number of layers in a stack which contains the defined obstacles.