Name
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. Agarwal | 1 | 5257 | 593.81 |
| Leonidas J. Guibas | 2 | 13084 | 1262.73 |
| Sariel Har-Peled | 3 | 2630 | 191.68 |
| Alexander Rabinovitch | 4 | 43 | 2.28 |
| Micha Sharir | 5 | 8405 | 1183.84 |