TY - GEN

T1 - Reporting intersecting pairs of 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 - 2001

Y1 - 2001

N2 - Let P={P 1,...,P m} be a set of m convex polytopes in Rd, 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/3logn + k), and an improved randomized algorithm with expected running time O((n log m + k)a(n)logn) (which is faster for small values of k). For d = 3, we present an O(n 8/5+e + k)-time algorithm, for any e>0. Our algorithms can be modified to count the number of intersecting pairs in O(n 4/3 log O(1) n) time for the planar case, and in O(n 8/5+e) time and R3. P.A. was also supported by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by NSF grants EIA-9870724, EIA-997287, and CCR-9732787, and by a grant from the U.S.-Israeli Binational Science Foundation. M.S. was supported by NSF Grant CCR-97-32101, by a grant from the Israel Science Fund (for a Center of Excellence in Geometric Computing), by the Hermann Minkowski-MINERVA Center for Geometry at Tel Aviv University, and by a grant from the U.S.-Israeli Binational Science Foundation.

AB - Let P={P 1,...,P m} be a set of m convex polytopes in Rd, 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/3logn + k), and an improved randomized algorithm with expected running time O((n log m + k)a(n)logn) (which is faster for small values of k). For d = 3, we present an O(n 8/5+e + k)-time algorithm, for any e>0. Our algorithms can be modified to count the number of intersecting pairs in O(n 4/3 log O(1) n) time for the planar case, and in O(n 8/5+e) time and R3. P.A. was also supported by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by NSF grants EIA-9870724, EIA-997287, and CCR-9732787, and by a grant from the U.S.-Israeli Binational Science Foundation. M.S. was supported by NSF Grant CCR-97-32101, by a grant from the Israel Science Fund (for a Center of Excellence in Geometric Computing), by the Hermann Minkowski-MINERVA Center for Geometry at Tel Aviv University, and by a grant from the U.S.-Israeli Binational Science Foundation.

U2 - 10.1007/3-540-44634-6_12

DO - 10.1007/3-540-44634-6_12

M3 - Conference contribution

SN - 3-540-42423-7

T3 - Lecture Notes in Computer Science

SP - 122

EP - 134

BT - Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings

A2 - Dehne, F.

A2 - Sack, J.R.

A2 - Tamassia, R.

PB - Springer

CY - Berlin

ER -