Search

In Sharir and Solomon (2015), Sharir and Solomon showed that the number of incidences between m distinct points and n distinct lines in R 4 is (1) O ∗ m 2 ∕ 5 n 4 ∕ 5 + m 1 ∕ 2 n 1 ∕ 2 q 1 ∕ 4 + m 2 ∕ 3 n 1 ∕ 3 s 1 ∕ 3 + m + n , provided that no 2-flat contains more than s lines, and no hyperplane or quadric contains more than q lines, where the O ∗ hides a multiplicative factor of 2 c log m for some absolute constant c . In this paper we prove that, for integers m , n satisfying n 9 ∕ 8 < m < n 3 ∕ 2 , there exist m points and n lines on the quadratic hypersurface in R 4 { ( x 1 , x 2 , x 3 , x 4 ) ∈ R 4 ∣ x 1 = x 2 2 + x 3 2 − x 4 2 } , such that (i) at most s = O ( 1 ) lines lie on any 2-flat, (ii) at most q = O ( n ∕ m 1 ∕ 3 ) lines lie on any hyperplane, and (iii) the number of incidences between the points and the lines is Θ ( m 2 ∕ 3 n 1 ∕ 2 ) , which is asymptotically larger than the upper bound in (1) , when n 9 ∕ 8 < m < n 3 ∕ 2 . This shows that the assumption that no quadric contains more than q lines (in the above mentioned theorem of Sharir and Solomon (2015)) is necessary in this regime of m and n . By a suitable projection from this quadratic hypersurface onto R 3 , we obtain m points and n lines in R 3 , with at most s = O ( 1 ) lines on a common plane, such that the number of incidences between the m points and the n lines is Θ ( m 2 ∕ 3 n 1 ∕ 2 ) . It remains an interesting question to determine if this bound is also tight in general. [ABSTRACT FROM AUTHOR]