ETSP on a Polygon in the Presence of a Polygonal Obstacle

We present a polynomial-time algorithm for a variant of the Euclidean traveling salesman tour where n vertices are on the boundary of a polygon P and m vertices form the boundary of a polygonal obstacle Q completely contained within P . In the worst case the algorithm needs O(nm + nm + m) time and O(n + m) space.