Incidences between points and circles in three and higher dimensions

Boris Aronov, Vladlen Koltun, Micha Sharir

    Research output: Contribution to conferencePaper

    Abstract

    We show that the number of incidences between m distinct points and n distinct circles in ℝ3 is O(m4/7n17/21 + m2/3n2/3 + m + n); the bound is optimal for m ≥ n3/2. This result extends recent work on point-circle incidences in the plane, but its proof requires a different analysis. The bound improves upon a previous bound, noted by Akutsu et al. [2] and by Agarwal and Sharir [1], but it is not as sharp (when m is small) as the recent planar bound of Aronov and Sharir [3]. Our analysis extends to yield the same bound (a) on the number of incidences between m points and n circles in any dimension d ≥ 3, and (b) on the number of incidences between m points and n arbitrary convex plane curves in ℝd, for any d ≥ 3, provided that no two curves are coplanar. Our results improve the upper bound on the number of congruent copies of a fixed tetrahedron in a set of n points in 4-space, and were already used to obtain a lower bound for the number of distinct distances in a set of n points in 3-space.

    Original languageEnglish (US)
    Pages116-122
    Number of pages7
    DOIs
    StatePublished - 2002
    EventProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, Spain
    Duration: Jun 5 2002Jun 7 2002

    Other

    OtherProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02)
    CountrySpain
    CityBarcelona
    Period6/5/026/7/02

    Keywords

    • Circles
    • Combinatorial geometry
    • Incidences
    • Three dimensions

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Incidences between points and circles in three and higher dimensions'. Together they form a unique fingerprint.

    Cite this