On Distinct Distances Between a Variety and a Point Set

2018/12/08 by Bryce McLaughlin, McLaughlin, Bryce, Mohamed Omar +1
Mathematics · Computer Science · #Mathematical Approximation and Integration #Computational Geometry and Mesh Generation #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1812.03371

Abstract

We consider the problem of determining the number of distinct distances between two point sets in ℝ² where one point set P₁ of size m lies on a real algebraic curve of fixed degree r, and the other point set P₂ of size n is arbitrary. We prove that the number of distinct distances between the point sets, D(P₁,P₂), satisfies D(P₁,P₂) = Ω(m^1/2n^1/2log^-1/2n) when m = Ω(n^1/2log^-1/3n) and D(P₁,P₂) = Ω(n^1/2 m^1/3) when m=O(n^1/2log^-1/3n) This generalizes work of Pohoata and Sheffer, and complements work of Pach and de Zeeuw.

Related

• Distinct Distances Between a Circle and a Generic Set
• Distinct distances between a collinear set and an arbitrary set of\n points
• Distinct distances for points lying on curves in ℝ^d -- the bipartite case
• Distinct Distances in R³ Between Quadratic and Orthogonal Curves
• Distinct distances on non-ruled surfaces and between circles