.1 200 OK date: Fri, 03 Jul 2026 06:25:21 GMT server: mw-web.codfw.main-54f6d45877-p6cj5 x-content-type-options: nosniff content-language: en accept-ch: reporting-endpoints: csp-report-to-endpoint='/w/api.php?action=cspreport&format=json'; content-security-policy: script-src 'unsafe-eval' blob: 'self' meta.wikimedia.org *.wikimedia.org *.wikipedia.org *.wikinews.org *.wiktionary.org *.wikibooks.org *.wikiversity.org *.wikisource.org wikisource.org *.wikiquote.org *.wikidata.org *.wikifunctions.org *.wikivoyage.org *.mediawiki.org mediawiki.org wikimedia.org *.wmflabs.org *.wmcloud.org *.toolforge.org wss://*.toolforge.org *.jsdelivr.net unpkg.com cdnjs.cloudflare.com raw.githubusercontent.com *.github.com code.jquery.com cdn.mathjax.org use.typekit.net fonts.cdnfonts.com use.fontawesome.com i.ytimg.com rsms.me doi.org localhost https://localhost:* http://localhost:* wss://localhost:* ws://localhost:* *.google.com *.gstatic.com *.googleapis.com *.translate.yandex.net yastatic.net ya.ru radically.github.io cdn.sammdot.ca cdn.fontshare.com viaf.org publicai-proxy.alaexis.workers.dev iiif.archive.org api.flickr.com live.staticflickr.com api.anthropic.com api.openai.com api.publicai.co catalogo.pusc.it parsifal.urbe.it opac.sbn.it overpass-api.de api.openrouteservice.org archive.org *.openstreetmap.org *.waymarkedtrails.org *.thunderforest.com registry.ipe.wiki analytics.ipe.wiki qlever.dev app.goacoustic.com wikipedia-archive.ourworldindata.org api.inaturalist.org inaturalist-open-data.s3.amazonaws.com validator.w3.org db.onlinewebfonts.com fontlibrary.org 'unsafe-inline' auth.wikimedia.org; default-src 'self' data: blob: upload.wikimedia.org https://commons.wikimedia.org meta.wikimedia.org *.wikimedia.org *.wikipedia.org *.wikinews.org *.wiktionary.org *.wikibooks.org *.wikiversity.org *.wikisource.org wikisource.org *.wikiquote.org *.wikidata.org *.wikifunctions.org *.wikivoyage.org *.mediawiki.org mediawiki.org wikimedia.org *.wmflabs.org *.wmcloud.org *.toolforge.org wss://*.toolforge.org *.jsdelivr.net unpkg.com cdnjs.cloudflare.com raw.githubusercontent.com *.github.com code.jquery.com cdn.mathjax.org use.typekit.net fonts.cdnfonts.com use.fontawesome.com i.ytimg.com rsms.me doi.org localhost https://localhost:* http://localhost:* wss://localhost:* ws://localhost:* *.google.com *.gstatic.com *.googleapis.com *.translate.yandex.net yastatic.net ya.ru radically.github.io cdn.sammdot.ca cdn.fontshare.com viaf.org publicai-proxy.alaexis.workers.dev iiif.archive.org api.flickr.com live.staticflickr.com api.anthropic.com api.openai.com api.publicai.co catalogo.pusc.it parsifal.urbe.it opac.sbn.it overpass-api.de api.openrouteservice.org archive.org *.openstreetmap.org *.waymarkedtrails.org *.thunderforest.com registry.ipe.wiki analytics.ipe.wiki qlever.dev app.goacoustic.com wikipedia-archive.ourworldindata.org api.inaturalist.org inaturalist-open-data.s3.amazonaws.com validator.w3.org db.onlinewebfonts.com fontlibrary.org en.wikibooks.org en.wikinews.org en.wikiquote.org en.wikisource.org en.wikiversity.org en.wikivoyage.org en.wiktionary.org www.mediawiki.org commons.wikimedia.org foundation.wikimedia.org incubator.wikimedia.org species.wikimedia.org wikimania.wikimedia.org www.wikidata.org www.wikifunctions.org auth.wikimedia.org; style-src 'self' data: blob: upload.wikimedia.org https://commons.wikimedia.org meta.wikimedia.org *.wikimedia.org *.wikipedia.org *.wikinews.org *.wiktionary.org *.wikibooks.org *.wikiversity.org *.wikisource.org wikisource.org *.wikiquote.org *.wikidata.org *.wikifunctions.org *.wikivoyage.org *.mediawiki.org mediawiki.org wikimedia.org *.wmflabs.org *.wmcloud.org *.toolforge.org wss://*.toolforge.org *.jsdelivr.net unpkg.com cdnjs.cloudflare.com raw.githubusercontent.com *.github.com code.jquery.com cdn.mathjax.org use.typekit.net fonts.cdnfonts.com use.fontawesome.com i.ytimg.com rsms.me doi.org localhost https://localhost:* http://localhost:* wss://localhost:* ws://localhost:* *.google.com *.gstatic.com *.googleapis.com *.translate.yandex.net yastatic.net ya.ru radically.github.io cdn.sammdot.ca cdn.fontshare.com viaf.org publicai-proxy.alaexis.workers.dev iiif.archive.org api.flickr.com live.staticflickr.com api.anthropic.com api.openai.com api.publicai.co catalogo.pusc.it parsifal.urbe.it opac.sbn.it overpass-api.de api.openrouteservice.org archive.org *.openstreetmap.org *.waymarkedtrails.org *.thunderforest.com registry.ipe.wiki analytics.ipe.wiki qlever.dev app.goacoustic.com wikipedia-archive.ourworldindata.org api.inaturalist.org inaturalist-open-data.s3.amazonaws.com validator.w3.org db.onlinewebfonts.com fontlibrary.org 'unsafe-inline'; object-src 'none'; report-uri /w/api.php?action=cspreport&format=json; report-to csp-report-to-endpoint last-modified: Fri, 03 Jul 2026 04:37:47 GMT content-type: text/html; charset=UTF-8 age: 0 accept-ranges: bytes x-cache: cp2047 miss, cp2047 miss x-cache-status: miss server-timing: cache;desc="miss", host;desc="cp2047" strict-transport-security: max-age=106384710; includeSubDomains; preload report-to: { "group": "wm_nel", "max_age": 604800, "endpoints": [{ "url": "https://intake-logging.wikimedia.org/v1/events?stream=w3c.reportingapi.network_error&schema_uri=/w3c/reportingapi/network_error/1.0.0" }] } nel: { "report_to": "wm_nel", "max_age": 604800, "failure_fraction": 0.05, "success_fraction": 0.0} set-cookie: WMF-Last-Access=03-Jul-2026;Path=/;HttpOnly;secure;Expires=Tue, 04 Aug 2026 00:00:00 GMT set-cookie: WMF-Last-Access-Global=03-Jul-2026;Path=/;Domain=.wikipedia.org;HttpOnly;secure;Expires=Tue, 04 Aug 2026 00:00:00 GMT set-cookie: WMF-DP=050;Path=/;HttpOnly;secure;Expires=Fri, 03 Jul 2026 00:00:00 GMT x-client-ip: 75.28.18.94 cache-control: private, s-maxage=0, max-age=0, must-revalidate, no-transform vary: Accept-Encoding,X-Subdomain,Cookie,Authorization,User-Agent set-cookie: GeoIP=US:TX:McKinney:33.20:-96.62:v4; Path=/; secure; Domain=.wikipedia.org set-cookie: NetworkProbeLimit=0.001;Path=/;Secure;SameSite=None;Max-Age=3600 set-cookie: WMF-Uniq=BS4HBE--ZR3bYruh3XxuZwOSAAAAAFvdib6_QyCuYSndZFRi7Bww7LME7hKfjE0A;Domain=.wikipedia.org;Path=/;HttpOnly;secure;SameSite=None;Expires=Sat, 03 Jul 2027 00:00:00 GMT transfer-encoding: chunked x-request-id: f97d44bc-4d5f-4d39-a1e5-4c2c26c4658f x-analytics: 8000 Gilbert–Johnson–Keerthi distance algorithm - Wikipedia Jump to content Main menu Main menu move to sidebar hide Navigation Main page Contents Current events Random article About Wikipedia Contact us Contribute Help Learn to edit Community portal Recent changes Upload file Special pages Search Search Appearance Donate Create account Log in Personal tools Donate Create account Log in Contents move to sidebar hide (Top) 1 Overview Toggle Overview subsection 1.1 Pseudocode 2 Illustration 3 See also 4 References 5 External links Toggle the table of contents Gilbert–Johnson–Keerthi distance algorithm 1 language Русский Edit links Article Talk English Read Edit View history Tools Tools move to sidebar hide Actions Read Edit View history General What links here Related changes Upload file Permanent link Page information Cite this page Get shortened URL Switch to legacy parser Print/export Download as PDF Printable version In other projects Wikidata item Appearance move to sidebar hide From Wikipedia, the free encyclopedia Method of determining minimum distance between two convex sets The Gilbert–Johnson–Keerthi distance algorithm is a method of determining the minimum distance between two convex sets , first published by Elmer G. Gilbert , Daniel W. Johnson, and S. Sathiya Keerthi in 1988. 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 . "Enhanced GJK" algorithms use edge information to speed up the algorithm by following edges when looking for the next simplex. This improves performance substantially for polytopes with large numbers of vertices. 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 avoids the multiplication of potentially small quantities and reduces the total CPU time of the GJK algorithm by an average of 10%, with improvements ranging from 5% to 25% in scenarios where the objects are in contact. [ 1 ] GJK algorithms are often used incrementally in simulation systems and video games. In this mode, the final simplex from a previous solution is used as the initial guess in the next iteration, or "frame". If the positions in the new frame are close to those in the old frame, the algorithm will converge in one or two iterations. This yields collision detection systems which operate in near-constant time. The algorithm's stability, speed, and small storage footprint make it popular for realtime collision detection , especially in physics engines for video games . Overview [ edit ] GJK relies on two functions: S u p p o r t ( s h a p e , d → ) {\displaystyle \mathrm {Support} (\mathrm {shape} ,{\vec {d}})} , which returns the point on shape which has the highest dot product with d → {\displaystyle {\vec {d}}} . N e a r e s t S i m p l e x ( s ) {\displaystyle \mathrm {NearestSimplex} (s)} , which takes a simplex s and returns the simplex on s closest to the origin, and a direction toward the origin normal to the new simplex. If s itself contains the origin, NearestSimplex accepts s and the two shapes are determined to intersect. The simplices handled by NearestSimplex may each be any simplex sub-space of ''n''</sup>"}},"i":0}}]}'> R n . For example in 3D, they may be a point, a line segment, a triangle, or a tetrahedron ; each defined by 1, 2, 3, or 4 points respectively. Pseudocode [ edit ] function GJK_intersection(shape p, shape q, vector initial_axis): vector A = Support(p, initial_axis) − Support(q, −initial_axis) simplex s = {A} vector D = −A loop : A = Support(p, D) − Support(q, −D) if dot(A, D) < 0: reject s = s ∪ {A} s, D, contains_origin := NearestSimplex(s) if contains_origin: accept Illustration [ edit ] The two types of collision and corresponding CSO face: face-vertex (top) and edge-edge (bottom). See also [ edit ] Minkowski Portal Refinement Hyperplane separation theorem References [ edit ] ↑ Montanari, Mattia; Petrinic, Nik; Barbieri, Ettore (30 June 2017). "Improving the GJK Algorithm for Faster and More Reliable Distance Queries Between Convex Objects". ACM Transactions on Graphics . 36 (3): 30:12. doi : 10.1145/3083724 . External links [ edit ] "A fast procedure for computing the distance between complex objects in three-dimensional space", Gilbert, Johnson and Keerthi - the initial publication "Computing the Distance between Objects", Oxford professor Stephen Cameron's implementation of GJK "A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)" A 52 minute video lecture on implementing Gilbert-Johnson-Keerthi "Improving the GJK algorithm for faster and more reliable distance queries between convex objects" , Montanari, Petrinic and Barbieri. "Collision Detection Accelerated: An Optimization Perspective" , Montaut, Le Lidec, Petrik, Sivic and Carpentier. This research article notably shows how the original GJK algorithm can be accelerated by exploiting Nesterov-type acceleration strategies, contributing to lowering the overall computational complexity of GJK. This applied mathematics –related article is a stub . You can help Wikipedia by adding missing information . v t e Retrieved from " https://en.wikipedia.org/w/index.php?title=Gilbert–Johnson–Keerthi_distance_algorithm&oldid=1351373013 " Categories : Geometric algorithms Convex geometry Applied mathematics Applied mathematics stubs Hidden categories: Articles with short description Short description is different from Wikidata All stub articles This page was last edited on 27 April 2026, at 14:56  (UTC) . Page was rendered with Parsoid . Text is available under the Creative Commons Attribution-ShareAlike 4.0 License ; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy . Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. , a non-profit organization. Privacy policy About Wikipedia Disclaimers Contact Wikipedia Legal & safety contacts Code of Conduct Developers Statistics Cookie statement Mobile view Search Search Toggle the table of contents Gilbert–Johnson–Keerthi distance algorithm 1 language Add topic 0