On Bipartite Distinct Distances in the Plane

Abstract

Given sets $\mathcal{P},\mathcal{Q}\subseteq {\mathbb{R}}^2$ of sizes $m$ and $n$ respectively, we are interested in the number of distinct distances spanned by $\mathcal{P}\times \mathcal{Q}$. Let $D(m,n)$ denote the minimum number of distances determined by sets in ${\mathbb{R}}^2$ of sizes $m$ and $n$ respectively, where $m\le n$. Elekes \cite{CircleGrids} showed that $D(m,n)=O(\sqrt{mn})$ when $m\le n^{1/3}$. For $m\ge n^{1/3}$, we have the upper bound $D(m,n)=O(n/\sqrt{\log n})$ as in the classical distinct distances problem. In this work, we show that Elekes' construction is tight by deriving the lower bound of $D(m,n)=\Omega (\sqrt{mn})$ when $m\le n^{1/3}$. This is done by adapting Székely's crossing number argument. We also extend the Guth and Katz analysis for the classical distinct distances problem to show a lower bound of $D(m,n)=\Omega (\sqrt{mn}/\log n)$ when $m\ge n^{1/3}$.

21 pages, 5 figures