An Iterative Algorithm for Computing Shortest Paths Through Line Segments in 3D

A version of the geometrical shortest path problem is to compute a shortest path connecting two points and passing a finite set of line segments in three dimensions. This problem arises in the pursuit path problem and also be used as a tool to finding shortest paths on polyhedral surface. This paper presents an iterative algorithm for dealing with the problem, particularly with large data. The idea is to simultaneously determines on each segment a point such that the length of the path successively connecting the points is decreased. We show that after a finite number of iterations, the algorithm converges to give an approximate solution. The algorithm is implemented in C++ and tested for large datasets. The numerical results are shown and discussed.