A Fast Procedure for Computing the Distance between Complex Objects in Three-dimensional Space

Authors

E.G. Gilbert, D.W. Johnson, S.S. Keerthi

Year

1988

Journal Paper

Algorithm

GJK

Source

IEEE Journal on Robotics and Automation

Identifiers

DOI 10.1109/56.2083

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.

Summary¶

Gilbert, Johnson, and Keerthi give a fast iterative procedure for computing the distance between convex objects, now known as the GJK algorithm. The method became a core primitive in collision detection and robotics because it works directly with support mappings rather than requiring explicit closest-feature enumeration.