Let P = {P_1,...,P_m} be a set of m convex polytopes in R~d, 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 P_i intersects P_j. For the planar case we describe a simple algorithm with running time O(n~(4/3) log~(2+ε) n + k), for any constant ε > 0, and an improved randomized algorithm with expected running time O((n log m + k)α(n) log n) (which is faster for small values of k). For d = 3, we present an O(n~(8/5+ε) + k)-time algorithm, for any ε > 0. Our algorithms can be modified to count the number of intersecting pairs in O(n~(4/3) log~(2+ε) n) time for the planar case, and in O(n~(8/5+ε)) time for the three-dimensional case.
展开▼
