Improved bounds for the union of locally fat objects in the plane

Boris Aronov, Mark De Berg, Esther Ezrar, Micha Sharir

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We show that, for any γ > 0, the combinatorial complexity of the union of n locally γ-fat objects of constant complexity in the plane is nγ4 2O(log n). For the special case of γ-fat triangles,the bound improves to O(n log n + n/γ log2 1/γ ).

    Original languageEnglish (US)
    Pages (from-to)543-572
    Number of pages30
    JournalSIAM Journal on Computing
    Volume43
    Issue number2
    DOIs
    StatePublished - 2014

    Keywords

    • Combinatorial geometry
    • Fat objects
    • Union complexity

    ASJC Scopus subject areas

    • Computer Science(all)
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Improved bounds for the union of locally fat objects in the plane'. Together they form a unique fingerprint.

    Cite this