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, vol. 1851 (2000), pp. 328-338, ISSN 0302-9743, ISBN 3540676902 [doi]
    (last updated on 2017/12/10)

    © 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