A performance comparison of three algorithms for proximity queries relative to convex polyhedra

This paper presents a comparative analysis relative to the experimental performances of an asymptotically fast and incremental algorithm, recently developed to compute collision translations for pairs of convex polyhedra. The algorithm may be worth considering because it solves a proximity problem which is less widely addressed than distance, as well as because of its peculiar computation strategy, well suited to work without initialization, but also endowed with an inherently embedded mechanism to exploit spatial coherence. Numerical data characterizing the behavior of the algorithm with respect to the complexity of the polyhedra have already been discussed elsewhere, thus here the main focus is on contrasting its performances with those of two popular algorithms designed to compute distances between polyhedra. Although the considered "yardsticks" answer different proximity queries, and although one of the techniques is meant to deal with general polyhedra, the results presented in this paper should help to assess the efficacy and potential of the approach under analysis. All the three algorithms, indeed, share the same kind of application context; moreover, on the basis of the asymptotic bounds discussed in the literature, distances and collision translations require similar computational efforts. A thorough comparison of the reported query times and, more significantly, of the corresponding trends seems to show that the behavior of the novel algorithm is quite interesting, especially when used without initialization, what should encourage further work on its peculiar approach