Distinct and repeated distances on a surface and incidences between points and spheres

Abstract

In this paper we show that the number of distinct distances determined by a set of $n$ points on a constant-degree two-dimensional algebraic variety $V$ (i.e., a surface) in ${\mathbb{R}}^3$ is at least $\Omega \left(n^{7/9}/\mathrm{polylog}n\right)$. This bound is significantly larger than the conjectured bound $\Omega (n^{2/3})$ for general point sets in ${\mathbb{R}}^3$. We also show that the number of unit distances determined by $n$ points on a surface $V$, as above, is $O(n^{4/3})$, a bound that matches the best known planar bound, and is worst-case tight in 3-space. This is in sharp contrast with the best known general bound $O(n^{3/2})$ for points in three dimensions. To prove these results, we establish an improved upper bound for the number of incidences between a set $P$ of $m$ points and a set $S$ of $n$ spheres, of arbitrary radii, in ${\mathbb{R}}^3$, provided that the points lie on an algebraic surface $V$ of constant degree, which does not have linear or spherical components. Specifically, the bound is $$O\left(m^{2/3}{n}^{2/3}+m^{1/2}{n}^{7/8}{\log }^{\beta }(m^4/n)+m+n+\sum _c|P_c|\cdot |S_c|\right),$$ where the constant of proportionality and the constant exponent $\beta$ depend on the degree of $V$, and where the sum ranges over all circles $c$ that are fully contained in $V$, so that, for each such $c$, $P_c=P\cap c$ and $S_c$ is the set of the spheres of $S$ that contain $c$. In addition, ${\sum }_c|P_c|=O(m)$ and ${\sum }_c|S_c|=O(n)$. This bound too improves upon earlier known bounds. These have been obtained for arbitrary point sets but only under severe restrictions about the spheres, which are dropped in our result. Another interesting application of our result is an incidence bound for arbitrary points and spheres in 3-space, where we improve and generalize the previous work of Apfelbaum and Sharir[AS].

References in corpus (8)

• On the Erdos distinct distance problem in the plane
• Polynomial partitioning for a set of varieties
• Cutting Algebraic Curves into Pseudo-segments and Applications
• Improved bounds for incidences between points and circles
• Algebraic curves, rich points, and doubly-ruled surfaces
• Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique
• On the use of Klein quadric for geometric incidence problems in two dimensions
• Multilevel polynomial partitions and simplified range searching

Cited by in corpus (3)

• Representation Complexity of Semi-algebraic Graphs
• Distinct Angles and Angle Chains in Three Dimensions
• A Reduction for the Distinct Distances Problem in ${\mathbb{R}}^d$