Reporting intersecting pairs of convex polytopes in two and three dimensions

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