A fast procedure for computing the distance between complex objects in three-dimensional space¶
Authors: E.G. Gilbert, D.W. Johnson, S.S. Keerthi
Published: 1988 (Journal Paper)
Source: IEEE Journal on Robotics and Automation
Algorithm: GJK
DOI: 10.1109/56.2083
Summary¶
Abstract¶
An algorithm for computing the Euclidean distance between a pair of convex sets in R^m is described. Extensive numerical experience with a broad family of polytopes in R^3 shows that the computational cost is approximately linear in the total number of vertices specifying the two polytopes. The algorithm has special features which makes its application in a variety of robotics problems attractive. These features are discussed and an example of collision detection is given.