An Improved Algorithm for Euclidean Shortest Paths of Visiting Line Segments in the Plane
Lijuan Wang, Li Huo, Dandan He · Journal of Convergence Information Technology · 2011
Let p and q be two points in the plane, how to compute the Euclidean shortest path between p and q which visits a sequence of disjoint segments given in the plane is the problem to be discussed. Based on rubber-band algorithm, in this paper, we proposed a rubber-band developed algorithm which adopted the thought of divide-and-conquer. Particularly, we have implemented it and we have applied 4 test data sets to test these two algorithms respectively, each test data set contains 100 groups of randomly generated test data, and in each group test data, the size of segments is more than 1000. The experiments demonstrated that the rubber-band developed algorithm was superior to the known same-purpose implementation.