Reporting intersecting pairs of convex polytopes in two and three dimensions

P.K. Agarwal, M. Berg, de, S. Har-Peled, M.H. Overmars, M. Sharir, J. Vahrenhold

    Research output: Contribution to journalArticleAcademicpeer-review

    7 Citations (Scopus)


    Let P={P(1),.....,P(m)) be a set of m convex polytopes in , 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/3log2+n+k), for any constant >0, and an improved randomized algorithm with expected running time O((nlogm+k)a(n)logn) (which is faster for small values of k). For d=3, we present an O(n8/5++k)-time algorithm, for any >0. Our algorithms can be modified to count the number of intersecting pairs in O(n4/3log2+n) time for the planar case, and in O(n8/5+) time for the three-dimensional case.
    Original languageEnglish
    Pages (from-to)195-207
    JournalComputational Geometry
    Issue number2
    Publication statusPublished - 2002


    Dive into the research topics of 'Reporting intersecting pairs of convex polytopes in two and three dimensions'. Together they form a unique fingerprint.

    Cite this