Reporting intersecting pairs of convex polytopes in two and three dimensions

Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; De Berg, M; Har-Peled, S; Overmars, MH; Sharir, M; Vahrenhold, J

Published Date

  • January 1, 2002

Published In

Volume / Issue

  • 23 / 2

Start / End Page

  • 195 - 207

International Standard Serial Number (ISSN)

  • 0925-7721

Digital Object Identifier (DOI)

  • 10.1016/S0925-7721(02)00049-4

Citation Source

  • Scopus