Cutting circles into pseudo-segments and improved bounds for incidences

Boris Aronov, Micha Sharir

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We show that n arbitrary circles in the plane can be cut into O(n3/2+ε) arcs, for any ε > 0, such that any pair of arcs intersects at most once. This improves a recent result of Tamaki and Tokuyama [20]. We use this result to obtain improved upper bounds on the number of incidences between m points and n circles. An improved incidence bound is also obtained for graphs of polynomials of any constant maximum degree.

    Original languageEnglish (US)
    Pages (from-to)475-490
    Number of pages16
    JournalDiscrete and Computational Geometry
    Volume28
    Issue number4
    DOIs
    StatePublished - Dec 2002

    ASJC Scopus subject areas

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

    Fingerprint Dive into the research topics of 'Cutting circles into pseudo-segments and improved bounds for incidences'. Together they form a unique fingerprint.

    Cite this