Growth distances: New measures for object separation and penetration

Quantitative measures for the separation and penetration of two convex objects are formulated. These measures, called separation and penetration growth distances, are closely related to traditional translational distance measures and share many of their desirable properties. The solution of a single optimization problem yields both the separation and penetration distances. For three-dimensional polytopes the optimization problem is a linear program in four variables whose asymptotic computational time is O(m), where m is the number of linear inequalities required to specify the two polytopes. This equals or far betters the known times required to compute translational distances: O(m) for separation and O(m(2) log m) for penetration. When the positioning of the two objects depends on configuration variables, the partial derivatives of the growth distances with respect to the configuration variables exist almost everywhere. Moreover, for polytopes they can be evaluated with little numerical effort. The large speed advantage for penetration growth distance creates new opportunities for the algorithmic separation of intersecting objects. Specifically, derivatives of the penetration growth distance can be used to construct motions which separate the objects. An application to path finding is described.