Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#313237] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Guibas, LJ; Har-Peled, 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. 328-338, ISSN 0302-9743, ISBN 3540676902 [doi]
    (last updated on 2018/08/22)

    © Springer-Verlag 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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320