TY - GEN
T1 - Computing the penetration depth of two convex polytopes in 3d
AU - Agarwal, Pankaj K.
AU - Guibas, Leonidas J.
AU - Har-Peled, Sariel
AU - Rabinovitch, Alexander
AU - Sharir, Micha
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
PY - 2000
Y1 - 2000
N2 - Let A and B be two convex polytopes in R3 with m and n facets, respectively. The penetration depth of A and B, denoted as π(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 π(A,B) in O(m3/4+ɛn3/4+ɛ + m1+ɛ + n1+ɛ) expected time, for any constant ɛ > 0. It also computes a vector t such that ||t|| = π(A,B) and int(A + t) ⊓ B = θ. We show that if the Minkowski sum B ⊗ (—A) has K facets, then the expected running time of our algorithm is O (K1/2+ɛm1/4n1/4 + m1+ɛ + n1+ɛ), for any ɛ > 0. We also present an approximation algorithm for computing π(A,B). For any δ > 0, we can compute, in time O(m + n + (log2(m + n))/δ), a vector t such that ||t|| < (1 + δ)π(A, B) and int(A +t) ⊓ B = θ. Our result also gives a δ-approximation algorithm for computing the width of A in time O(n + (log2 n)/δ), which is simpler and slightly faster than the recent algorithm by Chan.
AB - Let A and B be two convex polytopes in R3 with m and n facets, respectively. The penetration depth of A and B, denoted as π(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 π(A,B) in O(m3/4+ɛn3/4+ɛ + m1+ɛ + n1+ɛ) expected time, for any constant ɛ > 0. It also computes a vector t such that ||t|| = π(A,B) and int(A + t) ⊓ B = θ. We show that if the Minkowski sum B ⊗ (—A) has K facets, then the expected running time of our algorithm is O (K1/2+ɛm1/4n1/4 + m1+ɛ + n1+ɛ), for any ɛ > 0. We also present an approximation algorithm for computing π(A,B). For any δ > 0, we can compute, in time O(m + n + (log2(m + n))/δ), a vector t such that ||t|| < (1 + δ)π(A, B) and int(A +t) ⊓ B = θ. Our result also gives a δ-approximation algorithm for computing the width of A in time O(n + (log2 n)/δ), which is simpler and slightly faster than the recent algorithm by Chan.
UR - http://www.scopus.com/inward/record.url?scp=84956864746&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84956864746&partnerID=8YFLogxK
U2 - 10.1007/3-540-44985-X
DO - 10.1007/3-540-44985-X
M3 - Conference contribution
AN - SCOPUS:84956864746
SN - 3540676902
SN - 9783540676904
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 328
EP - 338
BT - Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings
A2 - Halldórsson, Magnús M.
PB - Springer
T2 - 7th Scandinavian Workshop on Algorithm Theory, SWAT 2000
Y2 - 5 July 2000 through 7 July 2000
ER -