A comparison of two fast algorithms for computing the distance between convex polyhedra

The problem of tracking the distance between two convex polyhedra is finding applications in many areas of robotics. The algorithm of Lin and Canny (1991) is a well-known fast solution to this problem, but by recasting the algorithms into configuration space, we show that a minor modification to the earlier algorithm of Gilbert, Johnson, and Keerthi (1988) also gives this algorithm the same expected cost.