TECHNICAL REPORT ARCHIVE


Improved Bounds for Incidences and Complexity of Many Faces in Arrangements of Circles and of Polynomial Arcs

TR-CIS-2000-06
Boris Aronov, Micha Sharir

pdf version of this paper

Abstract:
We derive improved upper bounds for the number of incidences between m points and n circles in the plane, and for the complexity of m distinct faces in an arrangement of circles. An improved incidence bound is also obtained for graphs of polynomials of any constant maximum degree.

Back to previous page