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=P1,.,Pm 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
Pi intersects Pj. For the planar
case we describe a simple algorithm with running time
O(n4/3 log n + k), and an improved algorithm with
running time O((n alpha(n) log n + k) log2 n). For
d=3, we present an O(n8/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
}