TY - JOUR

T1 - Reporting intersecting pairs of convex polytopes in two and three dimensions

AU - Agarwal, P.K.

AU - Berg, de, M.

AU - Har-Peled, S.

AU - Overmars, M.H.

AU - Sharir, M.

AU - Vahrenhold, J.

PY - 2002

Y1 - 2002

N2 - Let P={P(1),.....,P(m)) be a set of m convex polytopes in , for d=2,3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i,j) such that Pi intersects Pj. For the planar case we describe a simple algorithm with running time O(n4/3log2+n+k), for any constant >0, and an improved randomized algorithm with expected running time O((nlogm+k)a(n)logn) (which is faster for small values of k). For d=3, we present an O(n8/5++k)-time algorithm, for any >0. Our algorithms can be modified to count the number of intersecting pairs in O(n4/3log2+n) time for the planar case, and in O(n8/5+) time for the three-dimensional case.

AB - Let P={P(1),.....,P(m)) be a set of m convex polytopes in , for d=2,3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i,j) such that Pi intersects Pj. For the planar case we describe a simple algorithm with running time O(n4/3log2+n+k), for any constant >0, and an improved randomized algorithm with expected running time O((nlogm+k)a(n)logn) (which is faster for small values of k). For d=3, we present an O(n8/5++k)-time algorithm, for any >0. Our algorithms can be modified to count the number of intersecting pairs in O(n4/3log2+n) time for the planar case, and in O(n8/5+) time for the three-dimensional case.

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

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

M3 - Article

SN - 0925-7721

VL - 23

SP - 195

EP - 207

JO - Computational Geometry

JF - Computational Geometry

IS - 2

ER -