Algorithms for rapid computation of some distance functions between objects for path planning

This paper presents efficient algorithms for computing new types of distance measures. One of the measures denoted by d_rho⁺ (A, B) characterizes proximity of non-intersecting objects A and B taking into account their shapes. The second measure denoted by δ(σ; A, B) characterizes the penetration between two intersecting objects. The main contributions include: 1) O(m log n+n log m) algorithms to compute d_rho⁺ (A, B) and δ(σ; A, B) between convex polyhedra in ℜ³ having m and n vertices respectively; and 2) an efficient procedure to compute δ(σ; A, B) between non-polygonal objects described algebraically. We point out the utility of the measures for collision detection between a pair of objects