Improved bound for the union of fat triangles

Esther Ezra, Boris Aronov, Micha Sharir

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


    We show that, for any fixed δ > 0, the combinatorial complexity of the union of a triangles in the plane, each of whose angles is at least δ, is O(n2α(n) log* n). with the constant of proportionality depending oil δ. This considerably improves the twenty-year-old bound O(n log log n), due to Matoušek et al. [24, 25].

    Original languageEnglish (US)
    Title of host publicationProceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
    PublisherAssociation for Computing Machinery
    Number of pages8
    ISBN (Print)9780898719932
    StatePublished - 2011

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    ASJC Scopus subject areas

    • Software
    • General Mathematics


    Dive into the research topics of 'Improved bound for the union of fat triangles'. Together they form a unique fingerprint.

    Cite this