Close Euclidean Shortest Path Crossing an Ordered 3D Skew Segment Sequence

Tran, Nguyet; Dinneen, Michael J.

Given k skew segments in an ordered sequence E and two points s and t in a three-dimensional environment, for any [Formula: see text] , we study a classical geometric problem of finding a [Formula: see text] -approximation Euclidean shortest path between s and t, crossing the segments in E in order. Let L be the maximum Euclidean length of the segments in E and h be the minimum distance between two consecutive segments in E. The running time of our algorithm is [Formula: see text] . Currently, the running time of finding the exact shortest path for this problem is exponential. Thus, most practical algorithms of this problem are approximations. Among these practical algorithms, placing discrete points, named Steiner points, on every segment in E, then constructing a graph to find an approximate path between s and t, is most widely used in practice. However, using Steiner points will cause the running time of this approach to always depend on a polynomial function of the term [Formula: see text] , which is not a close optimal solution. Differently, in this paper, we solve the problem directly in a continuous environment, without using Steiner points, in terms of the running time depending on a logarithmic function of the term [Formula: see text] , which we call a close optimal solution.