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 . 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.
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics