An Efficient Unified Algorithm for the Minimum Euclidean Distance Between Two Collections of Compact Convex Sets

This paper presents an efficient unified algorithm for the minimum Euclidean distance between two collections of compact convex sets, each of which can be a collection of convex primitives, such as ellipsoids, capsules, and cylinders, or a collection of triangles (i.e., triangle mesh) or a collection of points (i.e., point cloud) as special cases. The Euclidean distance between two compact convex sets is defined to be the smallest translation to bring them into intersection if they are separated or to separate them if they intersect, which can be computed by the well-known Gilbert-Johnson-Keerthi (GJK) and expanding polytope (EP) algorithms, respectively. While existing algorithms are aimed at computing the minimum Euclidean distance for a specific type of collections, algorithms for mixed situations always remain vacant. We discover that the smallest translation direction between any two compact convex sets determines the planes to bound and separate some other sets in two collections and can help quickly identify sets that do not have the minimum distance. In this way, the minimum distance between two collections can be efficiently computed, hundreds to thousands of times faster than the brute-force search. The computational efficiency of the proposed algorithm is verified with a number of numerical experiments in various scenarios.