# Reporting intersecting pairs of polytopes in two and three dimensions

Published

Conference Paper

© Springer-Verlag Berlin Heidelberg 2001. Let P = {P1,…, Pm} 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 n + k), and an improved randomized algorithm with expected running time O((n logm + 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 logO(1) n) time for the planar case, and in O(n 8/5+ε ) time and R 3 .

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; de Berg, M; Har-Peled, S; Overmars, MH; Sharir, M; Vahrenhold, J

### Published Date

- January 1, 2001

### Published In

### Volume / Issue

- 2125 /

### Start / End Page

- 122 - 134

### Electronic International Standard Serial Number (EISSN)

- 1611-3349

### International Standard Serial Number (ISSN)

- 0302-9743

### International Standard Book Number 10 (ISBN-10)

- 3540424237

### International Standard Book Number 13 (ISBN-13)

- 9783540424239

### Digital Object Identifier (DOI)

- 10.1007/3-540-44634-6_12

### Citation Source

- Scopus