Loading...
Please wait, while we are loading the content...
Similar Documents
Improved bounds for incidences between points and circles (2013).
| Content Provider | CiteSeerX |
|---|---|
| Author | Sharir, Micha Sheffer, Adam Zahl, Joshua |
| Abstract | We establish an improved upper bound for the number of incidences between m points and n arbitrary circles in three dimensions. The previous best known bound, originally established for the planar case and later extended to any dimension ≥ 2, is O ∗ m 2/3 n 2/3 +m 6/11 n 9/11 +m+n (where the O ∗ (·) notation hides sub-polynomial factors). Since all the points and circles may lie on a common plane or sphere, it is impossible to improve the bound in R 3 without first improving it in the plane. Nevertheless, we show that if the set of circles is required to be “truly three-dimensional”in the sense that no sphere or plane contains more than q of the circles, for some q ≪ n, then the bound can be improved to O ∗ ( m 3/7 n 6/7 +m 2/3 n 1/2 q 1/6 +m 6/11 n 15/22 q 3/22 +m+n). For various ranges of parameters (e.g., when m = Θ(n) and q = o(n 7/9)), this bound is smaller than the best known two-dimensional worst-case lower bound Ω ∗ (m 2/3 n 2/3 +m+n). We present several extensions and applications of the new bound: (i) For the special case where all the circles have the same radius, we obtain the improved bound |
| File Format | |
| Publisher Date | 2013-01-01 |
| Access Restriction | Open |
| Content Type | Text |
