Enhancing GJK: computing minimum and penetration distances between convex polyhedra

Abstract

The problem of tracking the distance between two convex polyhedra is finding applications in many areas of robotics, including intersection detection, collision detection, and path planning. We present new results that confirm an almost-constant time complexity for an enhanced version of Gilbert, Johnson and Keerthi's (GJK) algorithm, and also describe modifications to the algorithm to compute measures of penetration distance.