Reporting Intersecting Pairs of Polytopes
in Two and Three Dimensions

Pankaj K. Agarwal,
Mark de Berg,
Sariel Har-Peled,
Mark H. Overmars,
Micha Sharir
and Jan Vahrenhold.

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 n + k), and an improved algorithm with
running time O((n alpha(n) log n + k) log^{2} n). For
d=3, we present an O(n^{8/5+µ}+k)-time
algorithm, for any µ >0.

@string{WADS_2001 = "Proc. 7th Workshop Algorithms Data Struct."}
@string{LNCS = "Lecture Notes in Computer Science"}
@inproceedings{abhosv-rippt-01
, author = "P.K. Agarwal and M.~de Berg and S.~{Har-Peled}
and M.H.~Overmars and M.~Sharir and J.~Vahrenhold"
, title = "Reporting Intersecting Pairs of Polytopes in
Two and Three Dimensions"
, pages = "122--134"
, booktitle = WADS_2001
, year = 2001
, editor = "F. Dehne and J.~Sack and R.~Tamassia"
, volume = 2125
, series = LNCS
}