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³ 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/4n^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²(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²(1/ delta)), which is simpler and faster than the recent algorithm by Chan [Ch00].

Postscript file

@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
}

Last modified: Fri Jul 7 18:10:40 EDT 2000