The union of convex polyhedra in three dimensions

Boris Aronov, Micha Sharir, Boaz Tagansky

    Research output: Contribution to journalArticle

    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 log k). This bound is almost tight in the worst case, as there exist collections of polyhedra with Ω(k3 + knα(k)) union complexity. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k3 + kn log k log n) expected time.

    Original languageEnglish (US)
    Pages (from-to)1670-1688
    Number of pages19
    JournalSIAM Journal on Computing
    Volume26
    Issue number6
    DOIs
    StatePublished - Dec 1997

    Keywords

    • Combinatorial complexity
    • Combinatorial geometry
    • Computational geometry
    • Convex polyhedra
    • Geometric algorithms
    • Randomized algorithms

    ASJC Scopus subject areas

    • Computer Science(all)
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'The union of convex polyhedra in three dimensions'. Together they form a unique fingerprint.

    Cite this