A 2-approximation algorithm for the zookeeper's problem

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.