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

Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    A compact body 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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
    Pages383-390
    Number of pages8
    StatePublished - 2004
    EventProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States
    Duration: Jun 9 2004Jun 11 2004

    Other

    OtherProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
    CountryUnited States
    CityBrooklyn, NY
    Period6/9/046/11/04

    Keywords

    • Combinatorial complexity
    • Fat objects
    • Union of objects

    ASJC Scopus subject areas

    • Software
    • Geometry and Topology
    • Safety, Risk, Reliability and Quality
    • Chemical Health and Safety

    Fingerprint 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