A New Algorithm for the Shortest Path of Touring Disjoint Convex Polygons

ABSTRACT

Given a start point s, a target point t, and a sequence of k disjoint convex polygons in the plane, finding the shortest path from s to t which visits each convex polygon in the given order is our focus. In this paper, we present an improved method to compute the shortest path based on the last step path maps by Dror et al. Instead of using of point location in previous algorithm, we propose an efficient method of locating the points in the path with linear query and make the data structures much simpler. Our improved algorithm gives the O(nk) running time which improves upon the time O(nklog(n/k)) by Dror etal., where n is the total number of vertices of all polygons. Furthermore, we have implemented this algorithm by programming. The result shows that our algorithm is correct and efficient..

Keywords: