Fast convex minimization to detect collisions between polyhedra

The subject of this paper is a fast algorithm for detecting collisions of two convex polyhedra translating in the space. A major feature is the novelty of the approach: collision detection for two convex bodies is reduced to collision detection for pairs of planar sections and minimization of a bivariate convex function; furthermore, most of the subproblems are solved using two-dimensional geometry. As proved by previous theoretical work, on this basis it is possible to design an algorithm, which runs in O(log^2n) time in the average and O(log^3n) in the worst case, where n is the total number of vertices. Here the focus is on a more practical version of the algorithm, which is particularly suited to plan collision-free paths on the basis of fine-grain descriptions of the objects in the workspace, as it is the case for the systems supported by sophisticated geometric modelers. After explaining the main ideas underlying the approach, a set of experimental results are presented and discussed in some depth.