The Shortest Path of Touring Lines given in the Plane
Lijuan Wang, Dandan He, Ansheng Deng, Tao Ning · The Open Cybernetics & Systemics Journal · 2015
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 2 ) running time can be obtained for this problem, which improves the previous O(n 3 logn) time.Our algorithm is simple and efficient.