This paper describes an efficient and fast algorithm for finding the minimum distance between two convex polyhedrons in a three dimensional space. To obtain the minimal distance, the proposed computational scheme is based on a direct approach to minimizing the distance function which produces a succession of optimal search directions along object boundaries. This algorithm combines the gradient projection method'; and an additional optimal search direction when the gradient projection method leads to a zigzagging phenomenon. In this case, the additional optimal search direction accelerates significantly the convergence of the process. Extensive numerical experiments with convex polyhedra show the performance of this algorithm when compared with that of previous approaches. The proposed algorithm may be very helpful in solving the computation of minimal distance between a pair of convex sets, the collision detection problem or to track the closest points of moving convex objects.
is defined as the 12-dimensional vector space over
