Touring a sequence of polygons

Given a sequence of k polygons in the plane, a start point s , and a target point, t , we seek a shortest path that starts at s , visits in order each of the polygons, and ends at t . If the polygons are disjoint and convex, we give an algorithm running in time O(kn log (n/k)) , where n is the total number of vertices specifying the polygons. We also extend our results to a case in which the convex polygons are arbitrarily intersecting and the subpath between any two consecutive polygons is constrained to lie within a simply connected region; the algorithm uses O(nk 2 log n) time. Our methods are simple and allow shortest path queries from s to a query point t to be answered in time O(k log n + m) , where m is the combinatorial path length. We show that for nonconvex polygons this "touring polygons" problem is NP-hard.The touring polygons problem is a strict generalization of some classic problems in computational geometry, including the safari problem, the zoo-keeper problem, and the watchman route problem in a simple polygon. Our new results give an order of magnitude improvement in the running times of the safari problem and the watchman route problem: We solve the safari problem in O(n 2 log n) time and the watchman route problem (through a fixed point s ) in time O(n 3 log n) , compared with the previous time bounds of O(n 3 ) and O(n 4 ) , respectively.

Authors

• Moshe Dror
• Alon Efrat
• Anna Lubiw
• Joseph S. B. Mitchell

Keywords

• NP-hardness
• polygons
• safari route
• shortest path
• traveling salesman problem
• watchman route