Gilbert–Johnson–Keerthi distance algorithm

Unlike many other distance algorithms, it does not require that the geometry data be stored in any specific format, but instead relies solely on a support function to iteratively generate closer simplices to the correct answer using the configuration space obstacle (CSO) of two convex shapes, more commonly known as the Minkowski difference.

GJK makes use of Johnson's distance sub algorithm, which computes in the general case the point of a tetrahedron closest to the origin, but is known to suffer from numerical robustness problems.

In 2017 Montanari, Petrinic, and Barbieri proposed a new sub algorithm based on signed volumes which avoid the multiplication of potentially small quantities and achieved a speedup of 15% to 30%.

In this mode, the final simplex from a previous solution is used as the initial guess in the next iteration, or "frame".

The algorithm's stability, speed, and small storage footprint make it popular for realtime collision detection, especially in physics engines for video games.