2003 | OriginalPaper | Buchkapitel
On the Complexity of Many Faces in Arrangements of Pseudo-Segments and Circles
verfasst von : Pankaj K. Agarwal, Boris Aronov, Micha Sharir
Erschienen in: Discrete and Computational Geometry
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.