Between a rock and a hard place
Jeff Abrahamson, William Clement Regli · 2005
We present a polynomial-time algorithm for a special case of the Euclidean traveling salesman problem in which a robot must visit all the vertices of two non-intersecting polygons without crossing any polygon edge. If both polygons are convex, one enclosing the other, our algorithm can find the optimal tour of the channel between them in time O(m^3+m^2n) and O(nm+m^2) space, where the exterior polygon has n vertices and the interior m vertices. In the more general case of non-convex polygons (not necessarily nested), the algorithm finds the exact optimum tour in O(n^2m + m^3) time and O(n^2+m^2) space. At the end we give several examples in the context of robot navigation.