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: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We show that the union of n translates of a convex body in ℝ3 can have Θ(n3) holes in the worst case, where a hole in a set X is a connected component of ℝ3 \ 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)
    Title of host publication32nd International Symposium on Computational Geometry, SoCG 2016
    EditorsSandor Fekete, Anna Lubiw
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    Pages10.1-10.16
    ISBN (Electronic)9783959770095
    DOIs
    StatePublished - Jun 1 2016
    Event32nd International Symposium on Computational Geometry, SoCG 2016 - Boston, United States
    Duration: Jun 14 2016Jun 17 2016

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    Volume51
    ISSN (Print)1868-8969

    Other

    Other32nd International Symposium on Computational Geometry, SoCG 2016
    CountryUnited States
    CityBoston
    Period6/14/166/17/16

    Keywords

    • Convex sets
    • Motion planning
    • Union complexity

    ASJC Scopus subject areas

    • Software

    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

    Aronov, B., Cheong, O., Dobbins, M. G., & Goaoc, X. (2016). The number of holes in the union of translates of a convex set in three dimensions. In S. Fekete, & A. Lubiw (Eds.), 32nd International Symposium on Computational Geometry, SoCG 2016 (pp. 10.1-10.16). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 51). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2016.10