Unions of fat convex polytopes have short skeletons

Boris Aronov, Mark de Berg

    Research output: Contribution to journalArticlepeer-review

    Abstract

    The skeleton of a polyhedral set is the union of its edges and vertices. Let P be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f max be the maximum complexity of any face of a polytope in P. We prove that the total length of the skeleton of the union of the polytopes in P is at most O(α(n)· log * n · log f max) times the sum of the skeleton lengths of the individual polytopes.

    Original languageEnglish (US)
    Pages (from-to)53-64
    Number of pages12
    JournalDiscrete and Computational Geometry
    Volume48
    Issue number1
    DOIs
    StatePublished - Jul 2012

    Keywords

    • Combinatorial complexity
    • Convex polytopes
    • Fat polytopes
    • Skeleton of union

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics

    Fingerprint

    Dive into the research topics of 'Unions of fat convex polytopes have short skeletons'. Together they form a unique fingerprint.

    Cite this