An efficient algorithm to compute the distance between two line segments

We present a fast algorithm for computing the shortest distance between two line segments in three-dimensional (3D) space. A Karush-Kuhn-Tucker (KKT) formulation is used to derive the algebraic equations at optimality. We show that these equations can be solved in closed-forms. The proposed algorithm gives not only the shortest distance, but also the coordinate of the optimal points. It can be applied on segments of different or equal lengths defined in 2D or 3D spaces. The computation of the shortest distance requires at most 18 multiplications or divisions and 14 additions. Extensive simulation tests show that the average computation time of the algorithm is about 8.46×10^-4 second on a computer running under 33 MHz.