Approximate Shortest Path Algorithms for Sequences of Pairwise Disjoint Simple Polygons
Xiuxia Pan, Fajie Li, Reinhard Klette · 2010
Assume that two points p and q are given and a finite ordered set of simple polygons, all in the same plane; the basic version of a touring-a-sequence-of-polygons problem (TPP) is to find a shortest path such that it starts at p, then visits these polygons in the given order, and ends at q. This paper describes four approximation algorithms for unconstrained versions of problems defined by touring an ordered set of polygons. It contributes to an approximate and partial answer to the previously open problem “What is the complexity of the touringpolygons problem for pairwise disjoint, simple and not necessarily convex polygons? ” by providing κ(ε)O(n) approximation algorithms for solving this problem, either for given start and end points p and q, or with allowing to have those variable, where n is the total number of vertices of the given k simple and pairwise disjoint polygons; κ(ε) defines the numerical accuracy in dependency of a selected ε> 0. 1 Contributions of this Paper According to [1], “one of the most intriguing open problems” identified by their results “is to determine the complexity of the fixed TPP for pairwise disjoint nonconvex simple polygons”. In this paper, we focus on the unconstrained fixed TPP (i.e., given start and end point of the path) and floating TPP (i.e., no given start or end point) under the condition that the convex hulls of the input polygons Pi are pairwise disjoint, but the polygons Pi itself may be nonconvex. Algorithm 2 in Section 2 partially answers the stated open problem for the fixed TPP by providing an approximation algorithm running in time κ(ε) · O(n), where n is the total number of vertices of all polygons. The solution technique proposed in [1] can only handle the fixed TPP, the fixed safari problem, and the fixed watchman route problem, all for convex polygons only. Our solution technique is suitable for solving both the fixed and the floating TPP with the same time complexity,