Touring Polygons, Parts Cutting, and q-Rectangles
Fajie Li, Reinhard Klette · 2007
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 κ(ε) · O(n), where n is the total number of vertices of the given polygons, and function κ(ε) is as κ(ε) = (L0 − L)/ε (1) where L0 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 κ(ε) ·O(k), where k is the number of layers in a stack which contains the defined obstacles.