On the union of κ-round objects in three and four dimensions

Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir

    Research output: Contribution to journalArticlepeer-review


    A compact set c in ℝd is κ-round if for every point p ∈ ∂ C there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ > 0, the combinatorial complexity of the union of n κ-round, not necessarily convex, objects in ℝ3 (resp., in ℝ4) of constant description complexity is O(n2+ε) (resp., O(n 3+ε)) for any ε > 0, where the constant of proportionality depends on ε, κ, and the algebraic complexity of the objects. The bound is almost tight in the worst case.

    Original languageEnglish (US)
    Pages (from-to)511-526
    Number of pages16
    JournalDiscrete and Computational Geometry
    Issue number4
    StatePublished - Dec 2006

    ASJC Scopus subject areas

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


    Dive into the research topics of 'On the union of κ-round objects in three and four dimensions'. Together they form a unique fingerprint.

    Cite this