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

    Polytopes
    Three-dimension
    Two Dimensions
    Convex Polytopes
    Randomized Algorithms
    Intersect
    Count
    Computing
    Output

    Cite this

    Agarwal, P. K., Berg, de, M., Har-Peled, S., Overmars, M. H., Sharir, M., & Vahrenhold, J. (2001). Reporting intersecting pairs of polytopes in two and three dimensions. In F. Dehne, J. R. Sack, & R. Tamassia (Eds.), Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings (pp. 122-134). (Lecture Notes in Computer Science; Vol. 2125). Berlin: Springer. https://doi.org/10.1007/3-540-44634-6_12
    Agarwal, P.K. ; Berg, de, M. ; Har-Peled, S. ; Overmars, M.H. ; Sharir, M. ; Vahrenhold, J. / Reporting intersecting pairs of polytopes in two and three dimensions. Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings. editor / F. Dehne ; J.R. Sack ; R. Tamassia. Berlin : Springer, 2001. pp. 122-134 (Lecture Notes in Computer Science).
    @inproceedings{007925b97adc4807a101e61665cd1346,
    title = "Reporting intersecting pairs of polytopes in two and three dimensions",
    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.",
    author = "P.K. Agarwal and {Berg, de}, M. and S. Har-Peled and M.H. Overmars and M. Sharir and J. Vahrenhold",
    year = "2001",
    doi = "10.1007/3-540-44634-6_12",
    language = "English",
    isbn = "3-540-42423-7",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "122--134",
    editor = "F. Dehne and J.R. Sack and R. Tamassia",
    booktitle = "Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings",
    address = "Germany",

    }

    Agarwal, PK, Berg, de, M, Har-Peled, S, Overmars, MH, Sharir, M & Vahrenhold, J 2001, Reporting intersecting pairs of polytopes in two and three dimensions. in F Dehne, JR Sack & R Tamassia (eds), Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings. Lecture Notes in Computer Science, vol. 2125, Springer, Berlin, pp. 122-134. https://doi.org/10.1007/3-540-44634-6_12

    Reporting intersecting pairs of polytopes in two and three dimensions. / Agarwal, P.K.; Berg, de, M.; Har-Peled, S.; Overmars, M.H.; Sharir, M.; Vahrenhold, J.

    Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings. ed. / F. Dehne; J.R. Sack; R. Tamassia. Berlin : Springer, 2001. p. 122-134 (Lecture Notes in Computer Science; Vol. 2125).

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

    TY - GEN

    T1 - Reporting intersecting pairs of polytopes in two and three dimensions

    AU - Agarwal, P.K.

    AU - Berg, de, M.

    AU - Har-Peled, S.

    AU - Overmars, M.H.

    AU - Sharir, M.

    AU - Vahrenhold, J.

    PY - 2001

    Y1 - 2001

    N2 - 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.

    AB - 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.

    U2 - 10.1007/3-540-44634-6_12

    DO - 10.1007/3-540-44634-6_12

    M3 - Conference contribution

    SN - 3-540-42423-7

    T3 - Lecture Notes in Computer Science

    SP - 122

    EP - 134

    BT - Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings

    A2 - Dehne, F.

    A2 - Sack, J.R.

    A2 - Tamassia, R.

    PB - Springer

    CY - Berlin

    ER -

    Agarwal PK, Berg, de M, Har-Peled S, Overmars MH, Sharir M, Vahrenhold J. Reporting intersecting pairs of polytopes in two and three dimensions. In Dehne F, Sack JR, Tamassia R, editors, Algorithms and data structures : 7th international workshop, WADS 2001, Providence RI, USA, August 8-10, 2001 : proceedings. Berlin: Springer. 2001. p. 122-134. (Lecture Notes in Computer Science). https://doi.org/10.1007/3-540-44634-6_12