Math @ Duke

Publications [#235445] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Berg, MD; HarPeled, 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. 195207, ISSN 09257721
(last updated on 2018/10/21)
Abstract: Let P= {Pi,..., Pm} be äset of m convex polytopes in Rd, ford = 2,3, with a total of n vertices. We present outputsensitive 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 threedimensional case. ©2002 Elsevier Science B.V. All rights reserved.


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

