A fast growth distance algorithm for incremental motions

A fast algorithm is presented for computing the growth distance between a p air of convex objects in three-dimensional space. The growth distance is a measure of both separation and penetration between objects. When the object s are polytopes represented by their faces, the growth distance is determin ed by the solution of a Linear Program (LP). This article presents a new ap proach to the solution of the LP. Under appropriate renditions, the computa tional time is very small and does not depend on the total number of faces of the objects, Compared to the existing algorithm for growth distance, the re is a time reduction of several orders of magnitude. This increase in spe ed is achieved by exploiting two resources: adjacency of the object faces a nd the computational coherence induced by incremental motions of the object s. Computational experiments show that the performance of the algorithm is in the same range as the fastest codes for the computation of the Euclidean separation distance.