Euclidean TSP on two polygons

We give an O(n2m+nm2+m2logm) time and O(n2+m2) space algorithm for finding the shortest traveling salesman tour through the vertices of two simple polygonal obstacles in the Euclidean plane, where n and m are the number of vertices of the two polygons. By obstacle, we mean that the tour may not cross between the interior and exterior of either polygon. We also consider the problem’s extension to higher dimensions, proving that, if P≠NP, constructing a shortest TSP tour on the vertices of two non-intersecting polytopes is NP-hard if the polytopes are similarly viewed as obstacles.