Incremental Convex Minimization for Computing Collision Translations of Convex Polyhedra

The subject of this paper is an asymptotically fast and incremental algorithm for computing collision translations of convex polyhedra, where the problem at hand is reduced to determining collision translations of pairs of planar sections and minimizing a bivariate convex function. There are two main reasons, in our view, why the algorithm is worth consideration. On the one hand, the addressed proximity measure, namely collision translation, is not as widely studied as distance. On the other, its peculiar computation strategy may be interesting in itself, being well suited to work without initialization and also endowed with an inherently embedded mechanism to exploit spatial coherence. After outlining the main ideas of this novel approach and providing an estimation of the computational costs, we summarize a broad set of numerical experiments meant to explore extensively the behavior of the algorithm, both without and with initialization. Finally, in order to assess the efficacy and the potential of the approach under analysis, the attained performances are contrasted with those of other popular algorithms designed to compute distances between polyhedra. A thorough comparison of the reported query times and, more significantly, of the corresponding trends shows that the behavior of the collision translation algorithm is quite interesting, especially when used without initialization or under variable coherence, which should encourage further work on this approach. running in average time for a total number of vertices, which corresponds to the best average-case complexity of the known techniques for answering similar proximity queries. Analogously to the distance algorithms, the proposed algorithm could be appropriate as a basic operation to plan collision-free paths, both online and offline, in the presence of fine-grain polyhedral descriptions of the objects. A complex representation of the workspace is indeed quite common for the geometric modelers based on CAD systems, as pointed out in [1], making it a critical goal to design fast techniques for computing proximity measures of primitive bodies. The algorithm may be especially useful to achieve more balanced performances across variable degrees of coherence [2], as it may be the case in real-time motion planning, but also the task of characterizing the configuration space offline can be approached by systematically solving simple collision detection problems in order to probe the structure of the free space, for example via randomized sampling strategies.