Algoritmo GJK
Un metodo che stabilisce se due corpi convessi collidono cercando l'origine all'interno della loro differenza di Minkowski.
Prende il nome da Elmer Gilbert, Daniel Johnson e Sathiya Keerthi, che lo descrissero nel 1988. L'idea chiave è che due insiemi convessi si intersecano esattamente quando la loro differenza di Minkowski contiene l'origine. GJK cerca l'origine senza mai costruire l'intera differenza: chiede soltanto punti di supporto, cioè il punto più lontano della forma in una data direzione, e fa crescere un piccolo simplesso (al massimo un tetraedro) che o racchiude l'origine o dimostra che è irraggiungibile.
Poiché tutto passa dalle funzioni di supporto, lo stesso codice gestisce poliedri, sfere, cilindri e capsule, cioè qualsiasi forma convessa. GJK fornisce la distanza quando le forme sono separate; per la profondità di penetrazione, una volta che si sovrappongono, lo si affianca a EPA. L'algoritmo è un pilastro dei motori fisici come Bullet e opera nella fase stretta.