Nordic Journal of Computing Bibliography

Abstract

Let A and B be two convex polytopes in R³ with m and n facets, respectively. The penetration depth of A and B, denoted as pi(A,B), is the minimum distance by which A has to be translated so that A and B do not intersect. We present a randomized algorithm that computes pi(A,B) in O(m^3/4+epsn^3/4+eps+m^1+eps+n^1+eps) expected time, for any constant eps > 0. It also computes a vector t such that ||t|| = pi(A,B) and int(A + t) intersect B = . We show that if the Minkowski sum B\oplus(-A) has K facets, then the expected running time of our algorithm is O(K^1/2+epsm^1/4n^1/4+m^1+eps+n^1+eps), for any eps > 0. We also present an approximation algorithm for computing pi(A,B). For any delta > 0, we can compute, in time O(m+n+(log²(m+n))/delta), a vector t such 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 of A in time O(n + (1/delta)log² (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.

Shortcuts: