On the complexity of many faces in arrangements of circles

P. K. Agarwal, B. Aronov, M. Sharir

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    The many-faces problem for arrangements of circles in the plane was studied. The complexity of many faces and the algorithmic problem arised in a variety of problems including three-dimensional arrangements. The improved bounds on the complexity of m distinct faces in an arrangement of n circles were obtained. The bounds coincide with the best known bounds for the number of incidences between m points and n circles.

    Original languageEnglish (US)
    Title of host publicationAnnual Symposium on Foundations of Computer Science - Proceedings
    Pages74-83
    Number of pages10
    StatePublished - 2001
    Event42nd Annual Symposium on Foundations of Computer Science - Las Vegas, NV, United States
    Duration: Oct 14 2001Oct 17 2001

    Other

    Other42nd Annual Symposium on Foundations of Computer Science
    CountryUnited States
    CityLas Vegas, NV
    Period10/14/0110/17/01

    ASJC Scopus subject areas

    • Hardware and Architecture

    Cite this

    Agarwal, P. K., Aronov, B., & Sharir, M. (2001). On the complexity of many faces in arrangements of circles. In Annual Symposium on Foundations of Computer Science - Proceedings (pp. 74-83)