On the Complexity of Many Faces in Arrangements of Pseudo-Segments and Circles

We obtain improved bounds on the complexity of many faces in an arrangement of pseudo-segments, circles, or unit circles. The bounds are worst-case optimal for unit circles; they are also worst-case optimal for the case of pseudo-segments except when the number of faces is very small, in which case our upper bound is a polylogarithmic factor away from the best-known lower bound. For general circles, the bounds nearly coincide with the best-known bounds for the number of incidences between points and circles.