Fast Computation of Shortest Path for Visiting Segments in the Plane

ABSTRACT

Let s and t be two points in the plane, how to compute the Euclidean shortest path between s and t which visits a sequence of segments given in the plane, is the problem to be discussed in this paper, especially, the situation of the adjacent segments intersect is the focus of our study. In this paper, we first analyze the degeneration applying rubber-band algorithm to solve the problem and introduce the algorithm for computing Euclidean shortest path with removing sufficiently small segments. Then based on rubber-band algorithm, we present a new algorithm for solving the degeneration and computing the ESP by crossing over two segments to deal with intersection and in our algorithm the adjacent segments order can be changed when they intersect. Furthermore, we have implemented the two algorithms and have applied a large test data to test them. The experiments demonstrate that our algorithm is more efficient and effective, and it has the same time complexity as the rubber-band algorithm.

Keywords: