2016/03/15 by Micha Sharir, Sharir, Micha, Noam Solomon +1 · 2 citations
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Polynomial and algebraic computation #Advanced Numerical Analysis Techniques
paper · pdf · doi:10.48550/arxiv.1603.04823
In this paper we establish an improved bound for the number of incidences between a set P of m points and a set H of n planes in \mathbb R3, provided that the points lie on a two-dimensional nonlinear irreducible algebraic variety V of constant degree. Specifically, the bound is O( m2/3n2/3 + m6/11n9/11logβ(m3/n) + m + n + ∑_ℓ |P_ℓ|⋅ |H_ℓ| ) , where the constant of proportionality and the constant exponent β depend on the degree of V, and where the sum ranges over all lines ℓ that are fully contained in V and contain at least one point of P, so that, for each such ℓ, P_ℓ = P∩ℓ and H_ℓ is the set of the planes of H that contain ℓ. In addition, ∑_ℓ |P_ℓ| = O(m) and ∑_ℓ |H_ℓ| = O(n). This improves, for this special case, the earlier more general bound of Apfelbaum and Sharir (see also Brass and Knauer as well as Elekes and Tóth). This is a generalization of the incidence bound for points and circles in the plane (cf. Aronov et al., Aronov and Sharir, Marcus and Tardos), and is based on a recent result of Sharir and Zahl on the number of cuts that turn a collection of algebraic curves into pseudo-segments. The case where V is a quadric is simpler to analyze, does not require the result of Sharir and Zahl, and yields the same bound as above, with β=2/11. We present an interesting application of our results to a problem, studied by Rudnev, on obtaining a lower bound on the number of distinct cross-ratios determined by n real points, where our bound leads to a slight improvement in Rudnev's bound.