Abstract
| Original language | English |
|---|---|
| Title of host publication | Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings |
| Editors | F. Dehne, J.R. Sack, R. Tamassia |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 122-134 |
| ISBN (Print) | 3-540-42423-7 |
| DOIs | |
| Publication status | Published - 2001 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 2125 |
| ISSN (Print) | 0302-9743 |
Fingerprint
Cite this
}
Reporting intersecting pairs of polytopes in two and three dimensions. / Agarwal, P.K.; Berg, de, M.; Har-Peled, S.; Overmars, M.H.; Sharir, M.; Vahrenhold, J.
Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings. ed. / F. Dehne; J.R. Sack; R. Tamassia. Berlin : Springer, 2001. p. 122-134 (Lecture Notes in Computer Science; Vol. 2125).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
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 -