### 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

*Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings*(pp. 122-134). (Lecture Notes in Computer Science; Vol. 2125). Berlin: Springer. https://doi.org/10.1007/3-540-44634-6_12

}

*Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings.*Lecture Notes in Computer Science, vol. 2125, Springer, Berlin, pp. 122-134. https://doi.org/10.1007/3-540-44634-6_12

**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.

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 -