Reporting intersecting pairs of polytopes in two and three dimensions

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

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Abstract

    Let P={P 1,...,P m} 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 P i intersects P j. For the planar case we describe a simple algorithm with running time O(n 4/3logn + k), and an improved randomized algorithm with expected running time O((n log m + k)a(n)logn) (which is faster for small values of k). For d = 3, we present an O(n 8/5+e + k)-time algorithm, for any e>0. Our algorithms can be modified to count the number of intersecting pairs in O(n 4/3 log O(1) n) time for the planar case, and in O(n 8/5+e) time and R3. P.A. was also supported by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by NSF grants EIA-9870724, EIA-997287, and CCR-9732787, and by a grant from the U.S.-Israeli Binational Science Foundation. M.S. was supported by NSF Grant CCR-97-32101, by a grant from the Israel Science Fund (for a Center of Excellence in Geometric Computing), by the Hermann Minkowski-MINERVA Center for Geometry at Tel Aviv University, and by a grant from the U.S.-Israeli Binational Science Foundation.
    Original languageEnglish
    Title of host publicationAlgorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings
    EditorsF. Dehne, J.R. Sack, R. Tamassia
    Place of PublicationBerlin
    PublisherSpringer
    Pages122-134
    ISBN (Print)3-540-42423-7
    DOIs
    Publication statusPublished - 2001

    Publication series

    NameLecture Notes in Computer Science
    Volume2125
    ISSN (Print)0302-9743

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

    Cite this