The Shortest Path of Touring Lines given in the Plane

ABSTRACT

Given two points p, q and a sequence of n lines (n>1) in the plane, we want to find the shortest path of touring all the given lines that starts at p and ends at q. In this paper, we solve the problem by reducing it to the problem of finding the shortest path that tours all the segments in a convex polygon from p to q. We first introduce how to construct the convex polygon. Then, we propose the solution to process the intersections of two adjacent segments by crossing over two segments. Finally, based on rubber-band algorithm, a new algorithm is proposed which can find the shortest path of touring segments in a convex polygon, and the O(n²) running time can be obtained for this problem, which improves the previous O(n³logn) time. Our algorithm is simple and efficient.

Keywords: