Paper Info
Title
Penetration depth of two convex polytopes in 3D
Abstract
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/4 n1/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 + (1/δ) log2(1/δ)), which is simpler and faster than the recent algorithm by Chan [3].
Year
Venue
Keywords
2000
Nord. J. Comput.
minimum distance,n facet,randomized algorithm,penetration depth,k facet,expected time,time o,convex polytopes,approximation algorithm,minkowski sum b,recent algorithm,convex polytope,collision detection,minkowski sum
Field
DocType
Volume
Randomized algorithm,Discrete mathematics,Combinatorics,Penetration depth,Regular polygon,Polytope,e,Mathematics,Minkowski addition
Journal
7
Issue
Citations
PageRank
3
32
1.56
References
Authors
10
5
Name
Order
Citations
PageRank
Pankaj K. Agarwal15257593.81
Leonidas J. Guibas2130841262.73
Sariel Har-Peled32630191.68
Alexander Rabinovitch4432.28
Micha Sharir584051183.84