Abstract

Incidences between sufficiently non-degenerate sets and applications

Abdul Basit
Rutgers University New Brunswick/Piscataway
Computer Science

We show bounds on point-plane and point-sphere incidences in
three dimensions. In particular, for $1 < k < n$, we say that a set of
planes (resp. spheres) is $k$-non-degenerate if no line (resp. circle)
is contained in $k$ planes (resp spheres) of the set. We show that for
every $\epsilon > 0$, the number of incidences between a set of $m$
points and a $k$-non-degenerate set of $n$ planes is $m^{4/5 + \epsilon}n^{3/5}k^{2/5} + mk + n$.

We use these to show bounds on a generalization of the unit distance
problem in three dimensions. In particular, we bound the number of
times a set of $k$ distances can occur among $n$ points in three
dimensions. (Note that the case $k = 1$ is the unit distances problem).