Gilbert-Johnson-Keerthi Algorithm

A classic iterative algorithm that tells whether two convex shapes intersect and computes the distance between them.

Published by Elmer Gilbert, Daniel Johnson, and S. Sathiya Keerthi in 1988, GJK needs only a ‘support function’ for each convex shape — given a direction, it returns the farthest point on the shape in that direction — so spheres, boxes, capsules, and convex meshes can all be handled uniformly. Its central fact is that two convex bodies intersect if and only if their Minkowski difference (the set formed by subtracting every point of B from every point of A) contains the origin. The algorithm iteratively builds points, line segments, triangles, and tetrahedra (simplices) inside that difference set, progressively closing in on the point nearest the origin, which gives either the separation distance or confirms intersection. It's fast and memory-efficient, making it a common core of narrow-phase collision detection in physics engines — MuJoCo's default collision pipeline is based on GJK plus EPA (the expanding polytope algorithm, used to compute penetration depth). Non-convex objects need convex decomposition first.

ExampleWhen checking clearance during motion planning, computing the distance between an arm link (represented as a convex hull) and a box on a table takes GJK only a few iterations, giving the planner a distance value to judge whether the path leaves enough margin.

Also called

GJK, GJK Distance Algorithm

Related

Collision Detection · Collision Checking · Convex Decomposition · Broad-phase / Narrow-phase Collision Detection · Collision Geometry (Collider) · Flexible Collision Library (FCL)

Sources

Wikipedia: Gilbert–Johnson–Keerthi distance algorithm
MuJoCo documentation: Computation (collision detection pipelines)