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

Math @ Duke



Publications [#235445] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Berg, MD; Har-Peled, S; Overmars, MH; Sharir, M; Vahrenhold, J, Reporting intersecting pairs of convex polytopes in two and three dimensions, Computational Geometry, vol. 23 no. 2 (2002), pp. 195-207, ISSN 0925-7721
    (last updated on 2018/10/21)

    Let P= {Pi,..., Pm} be äset of m convex polytopes in Rd, ford = 2,3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i, j) such that Pj intersects Pj. For the planar case we describe a simple algorithm with running time OC/i4β Iog2+e n + k), for any constant e > 0, and an improved randomized algorithm with expected running time O((/ilog;/i + £)<(»)log«) (which is faster for small values of k). For d = 3, we present an O(«8/5+e + &)-time algorithm, for any £> 0. Our algorithms can be modified to count the number of intersecting pairs in O(/i4β log2+£ n) time for the planar case, and in O(/i8/5+e) time for the three-dimensional case. ©2002 Elsevier Science B.V. All rights reserved.
ph: 919.660.2800
fax: 919.660.2821

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