Math @ Duke

Publications [#313237] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Guibas, LJ; HarPeled, S; Rabinovitch, A; Sharir, M, Computing the penetration depth of two convex polytopes in 3d,
in Seventh Scandinavian Workshop on Algorithm Theory,
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1851
(2000),
pp. 328338, ISSN 03029743, ISBN 3540676902 [doi]
(last updated on 2018/11/18)
Abstract: © SpringerVerlag Berlin Heidelberg 2000. 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 π(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(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 = π(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 (K 1/2+ɛ m 1/4 n 1/4 + m 1+ɛ + n 1+ɛ ), for any ɛ > 0. We also present an approximation algorithm for computing π(A,B). For any δ > 0, we can compute, in time O(m + n + (log 2 (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 + (log 2 n)/δ), which is simpler and slightly faster than the recent algorithm by Chan.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

