Home Bookmarks Papers Blog

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"}

, 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

Last modified: Fri Nov 14 10:58:50 CST 2014