The number of edges of many faces in a line segment arrangement

B. Aronov, H. Edelsbrunner, L. J. Guibas, M. Sharir

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We show that the maximum number of edges bounding m faces in an arrangement of n line segments in the plane is O(m2/3n2/3+nα(n)+nlog m). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is Ω(m2/3n2/3+nα(n)). In addition, we show that the number of edges bounding any m faces in an arrangement of n line segments with a total of t intersecting pairs is O(m2/3t1/3+nα(t/n)+nmin{log m,log t/n}), almost matching the lower bound of Ω(m2/3t1/3+nα(t/n)) demonstrated in this paper.

    Original languageEnglish (US)
    Pages (from-to)261-274
    Number of pages14
    JournalCombinatorica
    Volume12
    Issue number3
    DOIs
    StatePublished - Sep 1992

    Keywords

    • AMS subject classification code (1991): 52B05, 52C10, 68U05

    ASJC Scopus subject areas

    • Discrete Mathematics and Combinatorics
    • Computational Mathematics

    Fingerprint

    Dive into the research topics of 'The number of edges of many faces in a line segment arrangement'. Together they form a unique fingerprint.

    Cite this