A 2-approximation algorithm for the zookeeper's problem
Xuehou Tan · Information Processing Letters · 2006
Let P be a simple polygon, and let p be a set of disjoint convex polygons inside P, each sharing one edge with P. The zookeeper's route problem asks for a shortest route inside P that visits (but does not enter) each polygon in p. We present an O(n) time algorithm for computing a zookeeper's route of length at most 2 times that of the shortest zookeeper's route. Our result improves upon the previous approximation factor 6.