Computing the Penetration Depth of Two
Convex Polytopes in 3D

Pankaj K. Agarwal,
Leonidas J. Guibas,
Sariel Har-Peled,
Alexander Rabinovitch, and
Micha Sharir

Let A and B be two convex polytopes in
R^{3} 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+µ}n^{3/4+µ}+m^{1+µ}+n^{1+µ})
expected time, for any constant µ>0. It also computes a
vector t such that |t| = pi(A,B) and int(A + t) \cap
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+µ}m^{1/4}n^{1/4}+m^{1+µ}+n^{1+µ}),
for any µ>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^{2}(m+n))/ delta),
a vector t such that ||t|| <=(1+ delta) \pi(A,B)
and int(A+t) \cap B = Ø. Our result also gives
a delta-approximation algorithm for computing the width
of A in time O(n +(1/ delta) log^{2}(1/ delta)),
which is simpler and faster than the recent algorithm by Chan
[Ch00].

@Article{aghrs-cpdtc-00,
author = {P.K.~Agarwal and L.J.~Guibas and S.~Har-Peled
and A.~Rabinovitch and M.~Sharir},
title = {Penetration Depth of Two Convex Polytopes
in 3D},
journal = {Nordic J. Comput.},
volume = 7,
number = 3,
pages = {227--240},
year = 2000
}