The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Boris Aronov, Otfried Cheong, Michael Gene Dobbins, Xavier Goaoc

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We show that the union of n translates of a convex body in R3 can have Θ(n3) holes in the worst case, where a hole in a set X is a connected component of R3\ X. This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions.

    Original languageEnglish (US)
    Pages (from-to)104-124
    Number of pages21
    JournalDiscrete and Computational Geometry
    Volume57
    Issue number1
    DOIs
    StatePublished - Jan 1 2017

    Keywords

    • Convex sets
    • Motion planning
    • Union complexity

    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 'The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions'. Together they form a unique fingerprint.

    Cite this