Cutting circles into pseudo-segments and improved bounds for incidences

Boris Aronov; Micha Sharir

doi:10.1007/s00454-001-0084-1

Cutting circles into pseudo-segments and improved bounds for incidences

Boris Aronov, Micha Sharir

Research output: Contribution to journal › Article › peer-review

Abstract

We show that n arbitrary circles in the plane can be cut into O(n^3/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 language	English (US)
Pages (from-to)	475-490
Number of pages	16
Journal	Discrete and Computational Geometry
Volume	28
Issue number	4
DOIs	https://doi.org/10.1007/s00454-001-0084-1
State	Published - Dec 2002

ASJC Scopus subject areas

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

Access to Document

10.1007/s00454-001-0084-1

Cite this

@article{7efe9509d3a14cd38689e1dbaa1a3bb6,

title = "Cutting circles into pseudo-segments and improved bounds for incidences",

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.",

author = "Boris Aronov and Micha Sharir",

year = "2002",

month = dec,

doi = "10.1007/s00454-001-0084-1",

language = "English (US)",

volume = "28",

pages = "475--490",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Cutting circles into pseudo-segments and improved bounds for incidences

AU - Aronov, Boris

AU - Sharir, Micha

PY - 2002/12

Y1 - 2002/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0036883301&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036883301&partnerID=8YFLogxK

U2 - 10.1007/s00454-001-0084-1

DO - 10.1007/s00454-001-0084-1

M3 - Article

AN - SCOPUS:0036883301

SN - 0179-5376

VL - 28

SP - 475

EP - 490

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -

Cutting circles into pseudo-segments and improved bounds for incidences

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this