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.