AbstractLet

AandBbe two convex polytopes in R^{3}withmandnfacets, respectively. Thepenetration depthofAandB, denoted as pi(A,B), is the minimum distance by which A has to be translated so thatAandBdo not intersect. We present a randomized algorithm that computes pi(A,B) in O(m^{3/4+eps}n^{3/4+eps}+m^{1+eps}+n^{1+eps}) expected time, for any constanteps> 0. It also computes a vectortsuch that ||t|| = pi(A,B) and int(A+t) intersectB=. We show that if the Minkowski sum B\oplus(-A) hasKfacets, then the expected running time of our algorithm is O(K^{1/2+eps}m^{1/4}n^{1/4}+m^{1+eps}+n^{1+eps}), for anyeps> 0. We also present an approximation algorithm for computing pi(A,B). For anydelta> 0, we can compute, in time O(m+n+(log^{2}(m+n))/delta), a vectortsuch that ||t|| <= (1+delta) pi(A,B) and int(A+t) intersect B =. Our result also gives a delta-approximation algorithm for computing the width ofAin time O(n+ (1/delta)log^{2}(1/delta)), which is simpler and faster than the recent algorithm by Chan[3].

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.3 [Probability and Statistics]; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling; I.2.9 [Artificial Intelligence]: Robotics

Additional Key Words and Phrases: collision detection, Minkowski sum, geometric optimization

Selected references

- Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, and Micha Sharir. Algorithms for bichromatic line-segment problems polyhedral terrains. Algorithmica, 11(2):116-132, February 1994.