Given a sequence of k convex 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. This paper describes a simple method to compute the so-called last step shortest path maps, which were developed to solve this touring polygons problem by Dror et al. (STOC'2003). A major simplification is to avoid the (previous) use of point location algorithms. We obtain an O(kn) time solution to the problem for a sequence of disjoint convex polygons and an O(k~2n) time solution for possibly intersecting convex polygons, where n is the total number of vertices of all polygons. Our results improve upon the previous time bounds roughly by a factor of log n. Our new method can be used to improve the running times of two classic problems in computational geometry. We then describe an O(n(k + logn)) time solution to the safari problem and an O(n~3) time solution to the watchman route problem, respectively. The last step shortest path maps are further modified, so as to meet a new requirement that the shortest paths between a pair of consecutive convex polygons be contained in another bounding simple polygon.
展开▼
