Union of convex polyhedra in three dimensions

Boris Aronov, Micha Sharir

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k3+kn log2 k). This bound is almost tight in the worst case. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k3+kn log3 k) expected time.

    Original languageEnglish (US)
    Title of host publicationAnnual Symposium on Foundatons of Computer Science (Proceedings)
    Editors Anon
    PublisherPubl by IEEE
    Pages518-527
    Number of pages10
    ISBN (Print)0818643706
    StatePublished - Dec 1 1993
    EventProceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
    Duration: Nov 3 1993Nov 5 1993

    Publication series

    NameAnnual Symposium on Foundatons of Computer Science (Proceedings)
    ISSN (Print)0272-5428

    Other

    OtherProceedings of the 34th Annual Symposium on Foundations of Computer Science
    CityPalo Alto, CA, USA
    Period11/3/9311/5/93

    ASJC Scopus subject areas

    • Hardware and Architecture

    Cite this

    Aronov, B., & Sharir, M. (1993). Union of convex polyhedra in three dimensions. In Anon (Ed.), Annual Symposium on Foundatons of Computer Science (Proceedings) (pp. 518-527). (Annual Symposium on Foundatons of Computer Science (Proceedings)). Publ by IEEE.