Distinct Distances: Open Problems and Current Bounds
Adam Sheffer\thanks{California Institute of Technology
Pasadena
CA
{\sl adamsh@gmail.com
We survey the variants of Erd\H os' distinct distances problem and the current best bounds for each of those.
distProbs.tex
\documentclass[11pt]{article}
\usepackage{color,latexsym,amsmath,amssymb,path,url}

\newcommand{\ignore}[1]{}

\def\marrow{{\marginpar[\hfill$\longrightarrow$]{$\longleftarrow$}}}
\def\Adam#1{({\sc Adam says: }{\marrow\sf #1})}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% FORMAT
\setlength{\textwidth}{6.0in}
\setlength{\evensidemargin}{0.25in}
\setlength{\oddsidemargin}{0.25in}
\setlength{\textheight}{9.0in}
\setlength{\topmargin}{-0.5in}
%\setlength{\parskip}{2mm}
\setlength{\parskip}{0mm}
\setlength{\baselineskip}{1.7\baselineskip}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% THEOREMS ETC.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{conjecture}{Conjecture}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}

\newcounter{problems}
\newtheorem{problem}[problems]{Problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PROOFS
\newcommand{\Proof}[1]
        {
        \noindent
        \emph{Proof #1.}~
        }
\newsavebox{\smallProofsym}                     % smallproofsym.tex
\savebox{\smallProofsym}                        %
        {%                                      %
        \begin{picture}(7,7)                    %
        \put(0,0){\framebox(6,6){}}             %
        \put(0,2){\framebox(4,4){}}             %
        \end{picture}                           %
        }                                       %
\newcommand{\smalleop}[1]
        {
        \mbox{} \hfill #1~~\usebox{\smallProofsym}\!\!\!\!\!\!\
        }
\newenvironment{theProof}[1]
        {
        \Proof{#1}}{\smalleop{}
        \medskip

        }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% FIGURES
\usepackage{graphicx,psfrag}
\usepackage[rflt]{floatflt}

\newenvironment{myfigure}[1]
        {\begin{floatingfigure}{#1}}
        {\end{floatingfigure}}

\newcommand{\mycaption}[1]
        {\caption{\small #1}}
\newcommand{\placefig}[2]
        {\includegraphics[width=#2]{#1.eps}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  NUMBERS
\usepackage{dsfont}
\newcommand{\NN}{\ensuremath{\mathbb N}}
\newcommand{\ZZ}{\ensuremath{\mathbb Z}}
\newcommand{\RR}{\ensuremath{\mathbb R}}
\newcommand{\CC}{\ensuremath{\mathbb C}}
\newcommand{\PP}{\ensuremath{\mathbb P}}
\newcommand{\NNnull}{\NN_{^{_0}\!}}
\newcommand{\RRplus}   {\RR^{\!^+}}
\newcommand{\RRplusnull}{\RR^{\!^+}_{^{_0}\!}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PROBABILITY
\newcommand{\prr}       {{\mathrm{P\hspace{-0.05em}r}}}
\newcommand{\prrprime}  {{\mathrm{P\hspace{-0.05em}r}'}}
\newcommand{\pr}[1]     {{\,\prr\hspace{-0.05em}\left(#1\right)}}
\newcommand{\prprime}[1]{{\,\prrprime\hspace{-0.05em}\left(#1\right)}}
\newcommand{\ex}[1]     {{\,{\ensuremath{\mathbb E}}\!\left[#1\right]}}
\newcommand{\var}[1]    {{\,{\mathrm{var}}\!\left(#1\right)}}
\newcommand{\cond}      {\!\mid\!}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PAPER SPECIFIC

\newcommand{\pts}{\mathcal P}
\newcommand{\ptss}{\mathcal V}
\newcommand{\curves}{\mathcal C}
\newcommand{\rotations}{\mathcal R}

\def\hd{{\hat{D}}}

\newcommand{\s}{{\mathsf{subset}}}
\DeclareMathOperator*{\EE}{\mathbb{E}}
\newcommand{\lattice}{\mathcal L}

\def\eps{{\varepsilon}}


%%%%%%%%%%%%%%%%
\begin{document}
\pagenumbering{arabic}

\title{Distinct Distances: Open Problems and Current Bounds}

\author{
Adam Sheffer\thanks{California Institute of Technology, Pasadena, CA,
{\sl adamsh@gmail.com}.}
}

\maketitle

\begin{abstract}
We survey the variants of Erd\H os' distinct distances problem and the current best bounds for each of those.
\end{abstract}

\section{Introduction}
Given a set $\pts$ of $n$ points in $\RR^2$, let $D(\pts)$ denote the number of distinct distances that are determined by pairs of points from $\pts$. Let $D(n) = \min_{|\pts|=n}D(\pts)$;
that is, $D(n)$ is the minimum number of distinct distances that a set of $n$ points in $\RR^2$ can determine.
In his celebrated 1946 paper \cite{erd46}, Erd\H os derived the bound $D(n) = O(n/\sqrt{\log n})$.
More specifically, Erd\H os showed that a $\sqrt{n} \times \sqrt{n}$ integer lattice determines $\Theta(n/\sqrt{\log n})$ distinct distances (for more details, see Section \ref{sec:structure}).
Though almost 70 years have passed since Erd\H os considered this lattice structure, no configuration that determines an asymptotically smaller number of distinct distances was discovered.

For the celebrations of his 80th birthday, Erd\H os compiled a survey of his favorite contributions to mathematics \cite{erd96}, in which he wrote
 \begin{quotation}\em ``My most striking contribution to geometry is, no doubt, my problem on the number of distinct distances. This can be found in many of my papers on combinatorial and geometric problems."
 \end{quotation}

After 64 years and a series of increasingly larger lower bounds, Guth and Katz \cite{GK15} derived the bound $D(n) = \Omega(n/\log n)$, almost matching the current best upper bound (a comprehensive study of the previous bounds can be found in \cite{GIS11}).\footnote{See also William Gasarch's webpage: \url{http://www.cs.umd.edu/~gasarch/erdos_dist/erdos_dist.html}} To derive this bound, Guth and Katz developed several novel techniques, relying on tools from algebraic geometry, 19th century analytic geometry, and more.
Notice that a small gap of $O(\sqrt{\log n})$ remains between the current best lower and upper bounds.
%
\begin{problem} \label{pr:main}
Find the exact asymptotic value of $D(n)$.
\end{problem}

Since the problem is almost completely solved, one might wonder what is the purpose of this document.
The answer is that there are many challenging variants of the distinct distances problem that are still wide open (many of those posed by  Erd\H os).
For some of these variants, such as the ones presented in Section \ref{sec:structure}, even after several decades of work hardly anything non-trivial is known.
This document is meant to be dynamic, keeping track of the current best bounds and conjectures concerning the various distinct distances variants.

\ignore{Papers that study problems from the set that is surveyed in the first part of Section \ref{sec:rest} (i.e., problems that are still open) contain phrases such as ``Our ignorance in this area is really shocking!" \cite{EHP89} and ``It is rather frustrating that I got nowhere with..." \cite{erd87}.}

The main part of this survey is partitioned into six sections, each discussing a different family of problems. Section \ref{sec:structure} discusses the structure of planar point sets that determine a small number of distinct distances. Section \ref{sec:rest} surveys problems in which a planar point set is constrained in some manner. Section \ref{sec:HighD} considers distinct distances in higher dimensions. Section \ref{sec:subset} discusses subsets of points that determine every distance at most once.
Section \ref{sec:kl} surveys another family of restricted point sets, in which every subset of $k$ points determines at least $l$ distinct distances. Finally, Section \ref{sec:additional} presents problems that do not into fit any of the other sections.

For those who are only interested in the ``main" problems, it is the personal view of the author (and likely of others) that currently the most challenging/interesting distinct distances problems are Problem \ref{pr:OnLine} of Section \ref{sec:structure} and Problem \ref{pr:Rd} of Section \ref{sec:HighD}.
Another great collection of open problems related to distinct distances can be found in \cite[Sections 5.3 -- 5.6]{BMP05}.

A more general version of Problem \ref{pr:main} asks whether every planar point set $\pts$ contains a point that determines many distinct distances with the other points of $\pts$ (e.g., see Erd\H os \cite{erd87}). More formally, what is the minimum value $\hd(n)$, such that for every set $\pts$ of $n$ points in $\RR^2$ there exists a point $p \in \pts$ that determines at least $\hd(n)$ distinct distances with the other points of $\pts$?
A simple upper bound is $\hd(n) \le D(n) = O(n/\sqrt{\log n})$.
However, Guth and Katz's bound does not immediately imply a matching lower bound for $\hd(n)$.
The current best lower bound, obtained by Katz and Tardos \cite{KT04}, is $\hd(n) = \Omega(n^{(48-14e)/(55-16e)})\approx \Omega(n^{0.864})$.

\begin{problem} \label{pr:mainPnt}
Find the asymptotic value of $\hd(n)$.
\end{problem}

\section{The structure of point sets with few distinct distances} \label{sec:structure}

In this section we discuss characterizing the point sets that determine a small number of distinct distances.
This seems to be the family of problems for which we know the least; even after decades of studying them, hardly anything is known.
We say that a set $\pts$ of $n$ points in the plane is \emph{optimal} if $D(\pts) = D(n)$.
Since the asymptotic value of $D(n)$ is still unknown, we consider sets $\pts$ of $n$ points that satisfy $D(\pts)=O(n/\sqrt{\log{n}})$, and refer to such sets as \emph{near-optimal}.
All the point sets in this section are planar.


\begin{figure}[h]

\centerline{\placefig{grids}{0.9\textwidth}}
\vspace{-1mm}

\caption{\small \sf (a) An integer lattice.
(b) A lattice that can be obtained from (a) either by rotation and uniform scaling, or by removing from (a) every point whose coordinates sum to an odd number.
(c) A triangular lattice (of equilateral triangles).}
\label{fi:grids}
\vspace{-2mm}
\end{figure}

Erd\H os asked whether every optimal (or near-optimal) set ``has lattice structure" \cite{erd86}.
To make this question clearer, let us first consider some of the known near-optimal sets.
In the introduction we already mentioned that the $\sqrt{n} \times \sqrt{n}$ integer lattice (e.g., see Figure \ref{fi:grids}(a)) determines $O(n/\sqrt{\log n})$ distinct distances. This was observed by Erd\H os, who noticed that this is an immediate corollary of the following theorem from number theory.
%
\begin{theorem} \label{th:LandRam} {\bf (Landau-Ramanujan \cite{BR95,BMO11,Land08})}
The number of positive integers smaller than $n$ that are the sum of two squares is $\Theta(n/\sqrt{\log n})$.
\end{theorem}
%
Every distance in the $\sqrt{n} \times \sqrt{n}$ integer lattice is the square root of a sum of two squares between 0 and $n$. Thus, Theorem \ref{th:LandRam} implies that the number of distinct distances in this case is $\Theta(n/\sqrt{\log n})$.

The above implies that the $\sqrt{n} \times \sqrt{n}$ integer lattice is a near-optimal set.
More generally, for any integer $c \ge 1$, every $n$ point subset of the $c\sqrt{n} \times c\sqrt{n}$ integer lattice is a near-optimal set (since we can still apply Theorem \ref{th:LandRam} in such cases), and so are translations, rotations, and uniform scalings of such lattices.
For example, the lattice in Figure \ref{fi:grids}(b) can be obtained either by rotating and scaling the $\sqrt{n} \times \sqrt{n}$ integer lattice, or by removing from the $2\sqrt{n} \times 2\sqrt{n}$ integer lattice every point whose coordinates sum to an odd number.

We can further generalize the above. For any integer $r>1$, we define the rectangular lattice
\[ {\mathcal L}_r = \{ (i,j\sqrt{r}) \ \mid \ i,j\in\ZZ \quad \text{and} \quad  1 \le i,j \le \sqrt{n} \}. \]
%
The points of any such ${\mathcal L}_r$ span $\Theta(n/\sqrt{\log n})$ distinct distances (e.g., see \cite{Sblog14}).
By applying various transformations to these rectangular lattices, we get more near-optimal lattices. For example, the triangular lattice, which corresponds to the vertices in a tiling of equilateral triangles (e.g., see Figure \ref{fi:grids}(c)), can be obtained by taking a rectangular lattice and removing every other vertex.
After obtaining optimal sets for a few small values of $n$, Erd\H os and Fishburn \cite{EF96} conjectured that, for infinitely many values of $n$, there is an $n$-point subset of the triangular lattice that is optimal (that is, not just near-optimal).

For now, hardly anything is known regarding Erd\H os's conjecture that every near-optimal set has a lattice structure.
As a first step, Erd\H os \cite{erd86} suggested to determine whether every near-optimal point set contains $\Omega(\sqrt{n})$ points on a line, and thus most of the set can be covered by a small number of lines. Since this also appears to be quite difficult, Erd\H os asked whether there exists a line with $\Omega(n^\varepsilon)$ points of the set. Embarrassingly, even this weaker variant remains open.

\begin{problem} \label{pr:OnLine} {\bf (Erd\H os \cite{erd86})}
Prove or disprove: For a sufficiently small $\varepsilon>0$, every near-optimal point set contains $\Omega(n^\varepsilon)$ points on a common line.
\end{problem}

The current best bound is that for every near-optimal set $\pts$ of $n$ points, there exists a line $\ell$ such that $|\ell\cap\pts| = \Omega(\log n)$ (e.g., see \cite{Sblog14b}).
A recent result \cite{LSdZ15} states that for every near-optimal set $\pts$ of $n$ points and $0 < \alpha \le 1/4$, either there exists a line or a circle that contains $n^{\alpha}$ points of $\pts$, or there exist $n^{8/5-12\alpha/5-\eps}$ distinct lines that contain $\Omega(\sqrt{\log n})$ points of $\pts$. Thus, one way to solve Problem \ref{pr:OnLine} might be to prove that for any point set $\pts$ with  many lines that contain $\Omega(\sqrt{\log n})$ points of $\pts$ (and $\pts$ being near optimal), there exists a line containing $\Omega(n^{\eps})$ points of $\pts$.

Sheffer, Zahl, and de Zeeuw \cite{SZZ13} considered the complement problem --- proving that no line can contain many points of a near-optimal set. Specifically, they proved
that for every near-optimal set $\pts$ of $n$ points, every line contains  $O(n^{7/8})$ points of $\pts$. This bound was recently improved to  $O(n^{43/52})$ in \cite{RRNS15}.

\begin{problem} \label{pr:OnLine2}
Prove or disprove: For every near-optimal point set $\pts$and $\varepsilon>0$, every line contains $O(n^{0.5+\varepsilon})$ points of $\pts$.
\end{problem}

In Section \ref{sec:rest} we mention a result by Pach and de Zeeuw \cite{PZ13}, implying that if a set of $n$ points is contained in a constant-degree curve, then these points span $\Omega(n^{4/3})$ distinct distances, unless the curve contains a line or a circle.
That is, for every near-optimal set $\pts$ of $n$ points, any constant degree algebraic curve that does not contain lines and circles contains  $O(n^{3/4})$ points of $\pts$.
In \cite{SZZ13}, it is also proved that for every near-optimal set $\pts$ of $n$ points, every \emph{circle} contains  $O(n^{5/6})$ points of $\pts$.
By combining these three results, we obtain that for every near-optimal set $\pts$ of $n$ points, every constant-degree algebraic curve contains  $O(n^{43/52})$ points of $\pts$.

\begin{problem} \label{pr:OptimalCurves}
Prove or disprove: For every near optimal set $\pts$ of $n$ points and $\varepsilon>0$, every constant-degree curve contains $O(n^{0.5+\varepsilon})$ points of $\pts$.
\end{problem}



\section{Constrained sets of points} \label{sec:rest}

In this section we consider variants of the distinct distances problem where the point sets are constrained in some way. The current best bounds for these problems are listed in Table \ref{ta:sec2}; see Figure \ref{fi:sec2} and the text below for an explanation of the notation used in the table.
Unless stated otherwise, the point sets in this section are planar.

\begin{table}[h]
\begin{center}
\caption{The current best bounds for constrained sets of points.\label{ta:sec2}}
\vspace{2mm}

\begin{tabular}{|c|c|c|}
\hline
{\textbf {Variant}} & {\textbf {Lower bound}} & {\textbf {Upper bound}} \\
\hline\hline
$D_{\text{no3}\ell}(n)$  & $\displaystyle \lceil (n-1)/3\rceil$ (Szemer\'edi) & $\displaystyle \lfloor n/2\rfloor$ \cite{erd46} \\ \hline
$\hd_{\text{no3}\ell}(n)$  & $\displaystyle \lceil (n-1)/3\rceil$ (Szemer\'edi) & $\displaystyle \lfloor n/2\rfloor$ \cite{erd46} \\ \hline
$\hd_{\text{conv}}(n)$  & $\left(\frac{13}{36}+\frac{1}{22701}\right)n +O(1)$ \cite{Dum06,NPPZ11} & $\displaystyle \lfloor n/2\rfloor$ \cite{erd46} \\ \hline
$D_{\text{gen}}(n)$  & $\Omega(n)$ (trivial) & $\displaystyle n2^{O(\sqrt{\log n})}$ \cite{EFPR93} \\ \hline
$\hd_{\text{gen}}(n)$  & $\lceil (n-1)/3 \rceil$ (trivial) & $n-O(1)$ (trivial) \\ \hline
$D_{\text{para}}(n)$  & $\Omega(n)$ (trivial) & $\displaystyle O(n^2/\sqrt{\log n})$ \cite{Dum08} \\ \hline
$D_{\text{lines}}(n)$  & $\Omega(n^{4/3})$ \cite{SS13} & $\displaystyle O(n^2/\sqrt{\log n})$ \cite{Elek99} \\ \hline
$D_{\text{curves}}(n)$  & $\Omega(n^{4/3})$ \cite{PZ13} & $\displaystyle O(n^2/\sqrt{\log n})$ \cite{Elek99} \\ \hline

\end{tabular}
\end{center}
\vspace{-\baselineskip}
\end{table}

\begin{figure}[h]

\centerline{\placefig{sec2b}{0.92\textwidth}}
\vspace{-1mm}

\caption{\small \sf (a) The hierarchy of the constrained point sets in Section \ref{sec:rest}. Every arrow goes from a constrained problem to its generalization. (b) The vertices of a regular 10-gon.}
\label{fi:sec2}
\vspace{-2mm}
\end{figure}

\paragraph{General and convex position.} We begin with a set of problems that ask for exact bounds, instead of asymptotic ones; that is, where the ``fight" is for the best constant of proportionality. The hierarchy between the different types of constraints that are presented in this part is depicted in Figure \ref{fi:sec2}(a).
Denote by $D_{\text{no3}\ell}(n)$ the minimum number of distinct distances that can be determined by a set of $n$ points, no three of which are collinear (that is, $D_{\text{no3}\ell}(n) = \min_{|\pts|=n}D(\pts)$, where the minimum is taken over all sets of $n$ points containing no three collinear points).
Notice that the vertices of a regular $n$-gon, such as the set depicted in Figure \ref{fi:sec2}(b), satisfy this property and determine $\lfloor \frac{n}{2}\rfloor$ distinct distances, implying $D_{\text{no3}\ell}(n) \le \lfloor \frac{n}{2}\rfloor$. The current best lower bound, due to Szemer\'edi (communicated by Erd\H os in \cite{Erd75}; the proof can also be found in \cite[Chapter 13]{PA95}), is $D_{\text{no3}\ell}(n) \ge \lceil \frac{n-1}{3}\rceil$.
Szemer\'edi also conjectured that $D_{\text{no3}\ell}(n) = \lfloor \frac{n}{2}\rfloor$; see \cite{erd87,EHP89}.
%
\begin{problem} \label{pr:No3}
Find the exact value of $D_{ \text{\em no3}\ell}(n)$.
\end{problem}

As before, let $\hd_{\text{no3}\ell}(n)$ denote the maximum number satisfying that for any set $\pts$ of $n$ points, no three of which are collinear, there exists a point $p\in \pts$ such that there are at least $\hd_{\text{no3}\ell}(n)$ distinct distances between $\pts$ and $\pts\setminus\{p\}$.
%
\begin{problem} \label{pr:No3Pnt}
Find the exact value of $\hd_{\text{\em no3}\ell}(n)$.
\end{problem}

It can be easily noticed that the regular $n$-gon configuration implies $\hd_{\text{no3}\ell}(n) \le \lfloor \frac{n}{2}\rfloor$, and Szemer\'edi's bound for $D_{\text{no3}\ell}(n)$ also remains valid for $\hd_{\text{no3}\ell}(n)$. Thus, the current best bounds for Problems \ref{pr:No3} and \ref{pr:No3Pnt} are identical (as opposed to the case of Problems \ref{pr:main} and \ref{pr:mainPnt}).

Szemer\'edi's proof is so simple and elegant that it is hard to resist stating it here.
\begin{lemma}\label{le:no3}
$\hd_{\text{\em no3}\ell}(n) \ge \lceil \frac{n-1}{3}\rceil$
\end{lemma}
\begin{theProof}{\!\!}
Consider a set $\pts$ of $n$ points, no three of which are collinear. Let $x$ denote the minimum number satisfying that every point $p\in \pts$ determines at most $x$ distinct distances with the points of $\pts\setminus\{p\}$.

Let $T = \{(a,p,q)\in \pts^3 \mid |ap|=|aq|\}$, where $a,p,q$ are three distinct points and where $(a,p,q)$ and $(a,q,p)$ are counted as the same triple. The proof is based on double counting $|T|$, and we begin by deriving an upper bound for it. Given a pair of points $p,q\in\pts$, the triplet $(a,p,q)$ is in $T$ if and only if $a$ is on the perpendicular bisector of the segment $pq$. By the assumption, each such perpendicular bisector contains at most two points of $\pts$, which implies
\begin{equation}\label{eq:SzUp}
|T| \le 2 \binom{n}{2} = n(n-1).
\end{equation}
%
For the lower bound, notice that for every point $p\in\pts$, the points of $\pts\setminus\{p\}$ are contained in at most $x$ concentric circles around $p$. We denote these circles as $C_{p,1},\ldots,C_{p,x}$ and set $n_{p,i} = |C_{p,i} \cap \pts|$. Notice that $\sum_{i=1}^xn_{p,i} = n-1$ for every $p\in\pts$. By the Cauchy-Schwarz inequality, we have $\sum_{i=1}^x n_{p,i}^2 \ge \frac{1}{x}(n-1)^2$. This in turn implies
%
\begin{align} |T| = \sum_{p\in\pts}\sum_{i=1}^x \binom{n_{p,i}}{2} = \frac{1}{2}\sum_{p\in\pts}\sum_{i=1}^x (n_{p,i}^2-n_{p,i}) &\ge \frac{1}{2}\sum_{p\in\pts} \left( \frac{1}{x}(n-1)^2 - (n-1)\right) \nonumber \\
&= \frac{n(n-1)(n-1-x)}{2x}. \label{eq:SzLw}
\end{align}
%
Combining \eqref{eq:SzUp} and \eqref{eq:SzLw} immediately implies the assertion of the lemma.
\end{theProof}

Although no progress has been made with Problems \ref{pr:No3} and \ref{pr:No3Pnt} for several decades, more recent advances have been obtained for more restricted variants of them.
Similarly to $D_{\text{no3}\ell}(n)$, let $D_{\text{conv}}(n)$ denote the minimum number of distinct distances that can be determined by a set of $n$ points in (strict) convex position. Let $\hd_{\text{conv}}(n)$ denote the maximum number satisfying that for any set $\pts$ of $n$ points in convex position, there exists a point $p\in \pts$ such that there are at least $\hd_{\text{conv}}(n)$ distinct distances between $\pts$ and $\pts\setminus\{p\}$.

By considering the regular $n$-gon once again, we notice that $D_{\text{conv}}(n) \le \lfloor \frac{n}{2}\rfloor$ and that $\hd_{\text{conv}}(n) \le \lfloor \frac{n}{2}\rfloor$. Already in his 1946 paper, Erd\H os \cite{erd46} conjectured that $D_{\text{conv}}(n) = \lfloor \frac{n}{2}\rfloor$. This was proven by Altman \cite{Alt63,Alt72}, which led Erd\H os to suggest the stronger conjecture $\hd_{\text{conv}}(n) = \lfloor \frac{n}{2}\rfloor$.
Since for any set of points in convex position no three points can be collinear, we have $\hd_{\text{conv}}(n) \ge \hd_{\text{no3}}(n) \ge \lceil \frac{n-1}{3}\rceil$. In 2006, Dumitrescu \cite{Dum06} derived the improved bound $\hd_{\text{conv}}(n) \ge \lceil \frac{13n-6}{36}\rceil$. Recently, the slightly improved bound $\hd_{\text{conv}}(n) \ge \left(\frac{13}{36}+\frac{1}{22701}\right)n +O(1)$ was obtained by Nivasch, Pach, Pinchasi, and Zerbib \cite{NPPZ11}.

\begin{problem} \label{pr:conv}
Find the exact value of $\hd_{\text{\em conv}}(n)$.
\end{problem}

We say that a set of points is in \emph{general position} if no three points are collinear and no four points are cocircular. Denote by $D_{\text{gen}}(n)$ the minimum number of distinct distances that can be determined by a set of $n$ points in general position. The convex $n$-gon configuration is not in general position, and it is in fact unknown whether $D_{\text{gen}}(n) = \Theta(n)$ or not. The current best upper bound $D_{\text{gen}}(n) = n2^{O(\sqrt{\log n})}$ was derived by Erd\H os, F\"uredi, Pach, and Ruzsa \cite{EFPR93}. This bound is obtained by  considering a very different construction: taking an integer grid $G$ in a $d$-dimensional space (where $d$ is roughly $\sqrt{\log n}$), considering a subset $G'$ of the points of $G$ that lie on a common sphere, and projecting $G'$ on a generic plane. The generic projection guarantees that the resulting planar set is in general position, while the integer-grid-on-a-sphere structure implies a relatively small number of distinct distances.
For an easy lower bound, notice that $D_{\text{gen}}(n) \ge D_{\text{no3}}(n) = \Omega(n)$.

\begin{problem} \label{pr:gen}
Find the asymptotic value of $D_{\text{\em gen}}(n)$.
\end{problem}

Erd\H os \cite{erd87} also suggested to study the maximum number $\hd_{\text{\em gen}}(n)$ satisfying that for any set $\pts$ of $n$ points in general position, there exists a point $p\in \pts$ such that $\{p\}\times\pts$ determines at least $\hd_{\text{gen}}(n)$ distinct distances. Consider a point set $\pts$ in general position and a point $p\in \pts$. If $p$ has a distance of $d$ from four other points of $\pts$, then each of these four points is incident to the circle whose center is $p$ and radius is $d$, contradicting the general position assumption. Thus, a trivial lower bound is $\hd_{\text{\em gen}}(n) \ge \lceil (n-1)/3 \rceil$. No non-trivial bound is known for $\hd_{\text{\em gen}}(n)$ (neither a lower nor an upper bound), and when discussing the problem, Erd\H os \cite{erd87} wrote ``It is rather frustrating that I got nowhere with\ldots".

\begin{problem} \label{pr:gen}
Find the exact value of $\hd_{\text{\em gen}}(n)$.
\end{problem}

The point configuration that implies $D_{\text{gen}}(n) = n2^{O(\sqrt{\log n})}$ spans many duplicate vectors. This led to denoting by $D_{\text{para}}(n)$ the minimum number of distinct distances determined by a set of $n$ points in general position that do not determine any parallelograms.
Erd\H os, Hickerson, and Pach \cite{EHP89} asked whether $D_{\text{para}}(n)= o(n^2)$. This was recently confirmed by Dumitrescu \cite{Dum08}, who proved $D_{\text{para}}(n)= O(n^2/\sqrt{\log n})$ by considering, for prime $n$, the point set
\[ \left\{ (i,j) \mid i=0,1,\ldots,(n-1)/4, \ j= i^2 \hspace{-2mm}\mod n \right\}. \]
No bound better than the trivial $D_{\text{para}}(n)= \Omega(n)$ is known.
\begin{problem} \label{pr:para}
Find the asymptotic value of $D_{\text{\em para}}(n)$.
\end{problem}

We conclude this section with a conjecture by the author of this survey.
\begin{problem}
Prove or disprove: Let $\pts$ be a set of $n$ points, such that no two distinct pairs of points of $\pts$ have the same perpendicular bisector. Then for every $\eps>0$, we have $D(\pts)=\Omega(n^{2-\eps})$.
\end{problem}

\begin{figure}[h]

\centerline{\placefig{TwoLines}{0.7\textwidth}}
\vspace{-1mm}

\caption{\small \sf Two lines with $O(n)$ distinct distances.}
\label{fi:TwoLines}
\vspace{-2mm}
\end{figure}

\paragraph{Points on curves.}
We move to a different family of constrained point sets, where the points are restricted to being contained in a given curve.

Let $\pts_1$ and $\pts_2$ be two sets of $n$ points each, such that the points of $\pts_1$ (resp., $\pts_2$) lie on a line $\ell_1$ (resp., $\ell_2$). Let $D(\pts_1,\pts_2)$ denote the number of distinct distances between the pairs of $\pts_1\times\pts_2$ (that is, only distinct distances between points on different lines are considered).
When the two lines are either parallel or orthogonal, the points can be arranged such that $D(\pts_1,\pts_2) = \Theta(n)$; for example, see Figure \ref{fi:TwoLines}.
Purdy conjectured that if the lines are neither parallel nor orthogonal then $D(\pts_1,\pts_2) = \omega(n)$  (e.g., see \cite[Section 5.5]{BMP05}). Let us denote as $D_{\text{lines}}(n)$ the minimum number of distinct distances in such a scenario.
Elekes and R\'onyai \cite{ER00} proved Purdy's conjecture, though without deriving any specific superlinear lower bound. Later, Elekes \cite{Elek99} showed that $D_{\text{lines}}(n) = \Omega(n^{5/4})$.
Recently, Sharir, Sheffer, and Solymosi \cite{SS13} proved $D_{\text{lines}}(n) = \Omega(n^{4/3})$.
More generally, they derived the bound $\Omega(\min\{n^{2/3}m^{2/3},m^2,n^2\})$ for the asymmetric case where one line contains $n$ points and the other $m$ points (another recent asymmetric result, which is subsumed by the bound from \cite{SS13}, was derived by Schwartz, Solymosi, and de Zeeuw \cite{SSZ12}).
Elekes \cite{Elek99} also observed the upper bound $D_{\text{lines}}(n) = O(n^2/\sqrt{\log n})$.

\begin{problem} \label{pr:lines}
Find the asymptotic value of $D_{\text{\em lines}}(n)$.
\end{problem}

Generalizing Problem \ref{pr:lines}, we consider the minimum number of distinct distances between two sets of $n$ points, each on a constant degree algebraic curve in $\RR^2$ (the two curves may or may not be identical). We already know that there could be $O(n)$ distinct distances when the points are on parallel or orthogonal lines. In this more general scenario there exists a third exceptional case --- the case of two concentric circles. We denote by $D_{\text{\em curves}}(n)$ the minimum number of distinct distances between two sets of $n$ points, each on a constant degree algebraic curve, such that the two curves do not contain orthogonal lines, parallel lines, or concentric circles (this also implies that the two curves do not contain common lines or circles). Pach and de Zeeuw \cite{PZ13} extended the technique of \cite{SS13} to obtain $D_{\text{curves}}(n) = \Omega(n^{4/3})$. More generally, they derived the bound $\Omega(\min\{n^{2/3}m^{2/3},m^2,n^2\})$ for the asymmetric case when one curve contains $n$ points and the other $m$ points.

\begin{problem} \label{pr:curves}
Find the asymptotic value of $D_{\text{\em curves}}(n)$.
\end{problem}

In Section \ref{sec:HighD} we consider similar problems in higher dimensions.

\section{Higher dimensions} \label{sec:HighD}

In this section we consider higher-dimensional variants of the distinct distances problem.
Denote by $D_d(n)$ the minimum number of distinct distances that a set of $n$ points in $\RR^d$ can determine. Similarly to the planar case, the current best configuration for the $d$-dimensional case is an $n^{1/d} \times n^{1/d} \times \cdots \times n^{1/d}$ integer lattice. Every distance in this configuration is the square root of a sum of $d$ squares, each with a value between 0 and $n^{2/d}$. Therefore, the number of distinct distances that are determined by such a lattice is $O(n^{2/d})$, implying $D_d(n) = O(n^{2/d})$. This bound was already observed by Erd\H os in his 1946 paper \cite{erd46}, and is conjectured to be tight (for $d\ge 3$).

Solymosi and Vu \cite{SV08} derived the following recursive relations on $D_d(n)$.
%
\begin{theorem} \label{th:SV} {\bf (Solymosi and Vu \cite{SV08})}
(i) If $D_{d_0}(n) = \Omega(n^{\alpha_0})$, then for all $d>d_0$, we have
\[D_d(n) = \Omega\left( n^{\frac{2d}{(d+d_0+1)(d-d_0)+2d_0/\alpha_0}} \right). \]
%
(ii) If $D_{d_0}(n) = \Omega(n^{\alpha_0})$, then for all $d>d_0$ where $d-d_0$ is even, we have
\[D_d(n) = \Omega\left( n^{\frac{2(d+1)}{(d+d_0+2)(d-d_0)+2(d_0+1)/\alpha_0}} \right). \]
\end{theorem}
%
Recall that $D_2(n) = \Omega(n/\log{n})$. Combining this with Theorem \ref{th:SV}(i) implies $D_3(n) = \Omega^*(n^{3/5})$,\footnote{In the $\Omega^*(\cdot)$ notation we neglect polylogarithmic factors; although the logarithm in the denominator of the lower bound for $D_{2}(n)$ does not exactly fit the formulation of Theorem \ref{th:SV}, the proof remains valid.} while the above lattice example implies $D_3(n) = O(n^{2/3})$. These are the current best bounds for $D_3(n)$.
The current best bounds for larger values of $d$ are obtained by combining Theorem \ref{th:SV}(ii) with the bounds $D_2(n)=\Omega^*(n)$ and $D_3(n)=\Omega^*(n^{3/5})$ as base cases. That is, for even $d\ge4$ we have $D_d(n) = \Omega^*\left(n^{\frac{2d+2}{d^2+2d-2}}\right)$ and for odd $d\ge5$ we have $D_d(n) = \Omega^*\left(n^{\frac{2d+2}{d^2+2d-5/3}}\right)$.
Notice that as $d$ goes to infinity $D_d(n)$ approaches the conjectured bound $\Theta(n^{2/d})$.

\begin{problem} \label{pr:Rd}
Find the asymptotic value of $D_d(n)$.
\end{problem}

It seems possible that the techniques that were used by Guth and Katz \cite{GK15} for analyzing $D(n)$ could also be applied to the higher dimensional variant. However, so far it is still not clear how to extend some of the steps in this analysis.

Let $D_d^{o}(n)$ denote the minimum number of distinct distances that a set of $n$ points on a hypersphere in $\RR^d$ can determine. Tao \cite{Tao11} observed that the bound from \cite{GK15} remains valid when the point set is on a sphere in $\RR^3$ (or on a hyperbolic plane). That is, $D_3^{o}(n) = \Omega(n/\log{n})$. For a lower bound, place a set of $n$ points on a circle that is on the sphere, so that they form the vertices of a regular planar $n$-gon (recall figure \ref{fi:sec2}(b)). This implies $D_3^{o}(n) = O(n)$.

\begin{problem} \label{pr:sphere}
Find the asymptotic value of $D_3^o(n)$.
\end{problem}

Erd\H os, Fu\"redi, Pach, and Ruzsa \cite{EFPR93} proved $D_4^o(n) = O(n/\log \log n)$ and $D_d^o(n) = O(n^{2/(d-2)})$ for $d>4$.
These bounds are obtained by taking an integer lattice in $\RR^d$ and then choosing a sphere that contains many lattice points. No lower bound is known beyond the trivial $D_d^o(n) \ge D_d(n)$.

\begin{problem} \label{pr:sphereD}
Find the asymptotic value of $D_d^o(n)$ for $d\ge4$.
\end{problem}

\paragraph{Restricted point sets.}
Charalambides \cite{Chara13} considered the case where a set of $n$ points is contained in a constant-degree curve $C$ in $\RR^d$ (i.e., the $d$-dimensional variant of Problem \ref{pr:curves}).
He showed that if $C$ contains an \emph{algebraic helix} (see \cite{Chara13} for a description of this family of curves. In $\RR^2$ and $\RR^3$ the only algebraic helices are lines and circles) the points may determine only $O(n)$ distinct distances. On the other hand, if $C$ does not contain any algebraic helices,
the points on it determine $\Omega(n^{5/4})$ distinct distances. We denote by $D_{\text{\em curve}}^{(d)}(n)$ the minimum number of distinct distances that are determined by $n$ points on a $d$-dimensional
curve which does not contain an algebraic helix.

\begin{problem} \label{pr:curveD}
Find the asymptotic value of $D_{\text{\em curve}}^{(d)}(n)$.
\end{problem}
%
 In the rather special case of curves that have a polynomial parametrization, Raz, Sharir, and Solymosi \cite{RSS14} improve Charalambides' bound to $\Omega(n^{4/3})$. In this case, the only restriction on the curve is that it must not contain any lines (i.e., no other type of algebraic helix has such a parametrization).

It also seems natural to ask what happens when the point sets are restricted to surfaces. That is, the minimum number of distances between a set $\pts_1$ of $n$ points on a surface $S_1$ and a set $\pts_2$ of $n$ points on a surface $S_2$, both in $\RR^d$.
For example, consider the case where $S_1$ and $S_2$ are non-parallel planes in $\RR^3$. Then there are two orthogonal lines $\ell_1,\ell_2$ such that $\ell_1 \subset S_1$, $\ell_2 \subset S_2$, and $\ell_1 \cap \ell_2$ is a point on $S_1 \cap S_2$. By placing two sets of points on $\ell_1,\ell_2$ as depicted in Figure \ref{fi:TwoLines}, we obtain $\Theta(n)$ distinct distances. The same bound can be obtained between two spheres and between a sphere and a plane.
However, even these special cases are far from being settled, since an unrestricted set of $n$ points in $\RR^3$ can determine only $\Theta(n^{2/3})$ distinct distances.
No non-trivial bound is known for surfaces in $\RR^3$.

\begin{problem} \label{pr:surfs}
Consider two sets of points in $\RR^3$, each contained in a surface. For which surfaces can the number of distinct distances between the two sets be sublinear? For which surfaces this number must be superlinear?
\end{problem}




\section{Subsets with no repeated distances} \label{sec:subset}

This section surveys problems that concern point subsets that determine every distance at most once. Table \ref{ta:subset} lists the current best bounds for the problems that are presented in this section.

\begin{table}[h]
\begin{center}
\caption{Current best bounds for the problems of Section \ref{sec:subset}. \label{ta:subset}}
\vspace{2mm}

\begin{tabular}{|c|c|c|}
\hline
{\textbf {Variant}} & {\textbf {Lower bound}} & {\textbf {Upper bound}} \\
\hline\hline
$\s(n)$  & $\Omega(n^{1/3}/\log^{1/3} n)$ \cite{Chara12,GK15,LT95} & $O\left(\sqrt{n}/(\log n)^{1/4}\right)$ \cite{EG70} \\ \hline
\ignore{$\s_O(n)$  & $\Omega(n^{1/3}/\log^{1/3} n)$ \cite{Chara12,Tao11} & $O\left(\sqrt{n}\right)$ (trivial) \\ \hline}
$\s(\lattice)$  & $\Omega(n^{1/3}/\log^{1/3} n)$ \cite{EG70} & $O\left(\sqrt{n}/(\log n)^{1/4}\right)$ \cite{EG70} \\ \hline
$\s(\lattice_d)$  & $\Omega(n^{2/(3d)})$ \cite{LT95} & $O(n^{1/d})$ (trivial) \\ \hline
$\s_d(n)$ & $\Omega\left(n^{1/(3d-3)}(\log n)^{1/3 -2/(3d-3)}\right)$ \cite{CFGHUZ14} & $O(n^{1/d})$ (trivial) \\ \hline
$\s'(n)$  & $\Omega(n^{0.4315})$ & $O\left(\sqrt{n}/(\log n)^{1/4}\right)$ \cite{EG70} \\ \hline

\end{tabular}
\end{center}
\vspace{-\baselineskip}
\end{table}


\begin{figure}[h]

\centerline{\placefig{gridSubset}{0.5\textwidth}}
\vspace{-1mm}

\caption{\small \sf A set of 25 points and a subset of four points that span every distance at most once. No subset of five points has this property.}
\label{fi:gridSubset}
\vspace{-2mm}
\end{figure}

Given a set $\pts$ of points in $\RR^2$, let $\s(\pts)$ denote the size of the largest subset $\pts' \subset \pts$ such that every distance is spanned by the points of $\pts'$ at most once; that is, there are no points $a,b,c,d \in \pts'$ such that $|ab|=|cd|>0$ (including cases where $a=c$).
Figure \ref{fi:gridSubset} depicts a set of 25 points and a subset of four points that span every distance at most once.
Let $\s(n) = \min_{|\pts|=n}\s(\pts)$. In other words, $\s(n)$ is the maximum number satisfying the property that every set of $n$ points in the plane contains a subset of $\s(n)$ points that do not span any distance more than once.
Erd\H os \cite{Erd57,EG70,EP95} posed the following problem.

\begin{problem} \label{pr:subset} {\bf (Erd\H os)}
Find the asymptotic value of $\s(n)$.
\end{problem}

Let $\pts$ be a point set that spans $d$ distinct distances. Notice that if all of the distances that are spanned by the points of a subset $\pts' \subset \pts$ are unique, then the number of distances that are spanned by $\pts$ must be at least $\binom{|P'|}{2}$, or equivalently $|\pts'|=O\left(\sqrt{d}\right)$.
Let $\lattice$ be a $\sqrt{n}\times \sqrt{n}$ integer lattice. Recall that Erd\H os \cite{erd46} showed that the number of distinct distances that are spanned by $\lattice$ is $\Theta(n/\sqrt{\log n})$ (e.g., see Section \ref{sec:structure} of this document). Therefore, we have $\s(n) \le \s(\lattice) = O\left(\sqrt{n}/(\log n)^{1/4}\right)$.
Lefmann and Thiele \cite{LT95} derived the bound $\s(n)=\Omega(n^{0.25})$ by using a probabilistic argument. Dumitrescu \cite{Dum08} improved this bound to $\s(n)=\Omega(n^{0.288})$ by combining it with an upper bound of Pach and Tardos \cite{PT02} on the maximum number of isosceles triangles that can be spanned by a set of $n$ points. Recently, Charalambides \cite{Chara12} combined the probabilistic argument of Lefmann and Thiele with a result from Guth and Katz's distinct distances paper \cite{GK15}, to obtain the following improved result and simple proof.

\begin{theorem} \label{th:subset} {\bf (Charalambides \cite{Chara12})}
$\s(n)=\Omega(n^{1/3}/\log^{1/3} n)$.
\end{theorem}
\begin{theProof}{\!\!}
Consider a set $\pts$ of $n$ points in $\RR^2$. Similarly to the Elekes-Sharir reduction, we define the set
\[ Q_1 = \left\{ (a,b,c,d)\in \pts^4 \ \big| \ |ab|=|cd|>0 \right\}, \]
%
such that every quadruple of $Q_1$ consists of four distinct points. Guth and Katz \cite{GK15} proved that $|Q_1|=O(n^3\log n)$ (also for the case where $Q_1$ is allowed to contain quadruples where not all four points are distinct). Let $Q_2$ be the set of isosceles and equilateral triangles that are spanned by points of $\pts$.

Let $\pts' \subset \pts$ be a subset that is obtained by selecting every point of $\pts$ with a probability $0 < p <1$ that will be determined below.
We have $\EE[|\pts'|] = p n$. Let $Q_1' \subset Q_1$ be the set of quadruples of $Q_1$ that contain only points of $\pts'$. Every quadruple of $Q_1$ is in $Q_1'$ with a probability of $p^4$, so $\EE[|Q_1'|] \le \alpha p^4 n^3\log{n}$, for a sufficiently large constant $\alpha$. Let $Q_2'$ be the set of triangles of $Q_2$ that contain only points of $\pts'$. The bound of Pach and Tardos implies $\EE[|Q_2'|] \le \alpha p^3 n^{2.137}$, for sufficiently large $\alpha$.
Notice that the points of $\pts'$ span every distance at most once if and only if $|Q_1'|=|Q_2'|=0$.
By linearity of expectation, we have
\begin{equation*}
\EE\left[|\pts'|-|Q_1'|-|Q_2'|\right]\ge p n - \alpha p^4 n^3\log{n} - \alpha p^3 n^{2.137}.
\end{equation*}
%
By setting $p=1/(2\alpha n^2\log n)^{1/3}$, for sufficiently large $n$ we obtain
\begin{equation*}
\EE\left[|\pts'|-|Q_1'|-|Q_2'|\right]> \frac{n^{1/3}}{3(\alpha\log n)^{1/3}}.
\end{equation*}
Therefore, there exists a subset $\pts' \subset \pts$ for which $|\pts'|-|Q_1'|-|Q_2'|\ge \frac{n^{1/3}}{3(\alpha\log n)^{1/3}}$. Let $\pts''$ be a subset of $\pts'$ that is obtained by removing from $\pts'$ a point from every element of $Q_1'$ and $Q_2'$. The subset $\pts''$ does not span any repeated distances and contains $\Omega(n^{1/3}/\log^{1/3} n)$ points of $\pts$.
\end{theProof}

\ignore{%--------------------------------------
Let $\s_O(n)$ denote the maximum number satisfying the property that every set of $n$ points on a sphere in $\RR^3$ contains a subset of $\s_O(n)$ points that do not span any distance more than once. Charalambides \cite{Chara12} showed that a simple extension of the proof of Theorem \ref{th:subset} implies $\s(n)=\Omega(n^{1/3}/\log^{1/3} n)$. This requires an extension of Guth and Katz's distinct distances result to points on a sphere, as derived by Tao \cite{Tao11}. Let $\pts_r$ be the set of vertices of a regular $n$-gon in $\RR^3$. It can be easily verified that the points of $\pts_r$ determine $O(n)$ distinct distances and are contained in a common sphere. This implies $\s_O(n)=O(\sqrt{n})$.

\begin{problem}
Find the asymptotic value of $\s_O(n)$.
\end{problem} }%------------------------------------

Erd\H os and Guy \cite{EG70} considered the following special case of Problem \ref{pr:subset}.
%
\begin{problem} \label{pr:Lat}{\bf (Erd\H os and Guy \cite{EG70})}
Find the asymptotic value of $\s(\lattice)$, where $\lattice$ is a $\sqrt{n}\times \sqrt{n}$ integer lattice.
\end{problem}

As mentioned above, the current best upper bound for $\s(\lattice)$ is $O\left(\sqrt{n}/(\log n)^{1/4}\right)$. Erd\H os and Guy \cite{EG70} derived the bound $\s(\lattice) = \Omega(n^{1/3-\varepsilon})$, which was later improved by Lefmann and Thiele \cite{LT95} to $\s(\lattice) = \Omega(n^{1/3})$. This bound is still marginally better than the bound implied by Theorem \ref{th:subset}.

Erd\H os and Guy \cite{EG70} also considered the higher dimensional variant of Problem \ref{pr:Lat}. That is, they considered a $d$-dimensional lattice $\lattice_d$ of the form $n^{1/d}\times \cdots \times n^{1/d}$. Similarly to the planar case, Erd\H os and Guy \cite{EG70} derived the bound $\s(\lattice_d) = \Omega(n^{2/(3d)-\varepsilon})$, and this was later improved by Lefmann and Thiele \cite{LT95} to $\s(\lattice_d) = \Omega(n^{2/(3d)})$.
It is simple to show that the points of $\lattice_d$ span $O(n^{2/d})$ distinct distances (e.g., see Section \ref{sec:HighD} of this document), which implies $\s(\lattice_d) = O(n^{1/d})$.

\begin{problem}{\bf (Erd\H os and Guy \cite{EG70})}
Find the asymptotic value of $\s(\lattice_d)$, where $\lattice_d$ is an $n^{1/d}\times \cdots \times n^{1/d}$ integer lattice.
\end{problem}

We can also consider the higher dimensional variant of Problem \ref{pr:subset}. Let $\s_d(n)$ denote the maximum number satisfying the property that every set of $n$ points in $\RR^d$ contains a subset of $\s_d(n)$ points that do not span any distance more than once.
Thiele \cite[Theorem 4.33]{Thiele95} proved the lower bound $\s_d(n)=\Omega(n^{1/(3d-2)})$.
Recently, this was improved by Conlon, Fox, Gasarch, Harris, Ulrich, and Zbarsky \cite{CFGHUZ14} to $\s_d(n)=\Omega\left(n^{1/(3d-3)}(\log n)^{1/3 -2/(3d-3)}\right)$.
The current best upper bound is $\s_d(n)\le \s(\lattice_d) = O(n^{1/d})$.
%
\begin{problem}
Find the asymptotic value of $\s_d(n)$ for $d\ge 3$.
\end{problem}

In the open problems book of Brass, Moser, and Pach \cite{BMP05}, they offer a problem of a similar flavor. Let $\s'(n)$ denote the maximum number satisfying the property that every set of $n$ points in the plane contains a subset of $\s'(n)$ points that do not span any isosceles triangles.

\begin{problem} {\bf (Brass, Moser, and Pach \cite{BMP05})}
Find the asymptotic value of $\s'(n)$.
\end{problem}

For a trivial upper bound, we have $\s'(n) \le s(n) = O\left(\sqrt{n}/(\log n)^{1/4}\right)$. By adapting the proof of Theorem \ref{th:subset} (i.e., removing $Q_1$ from the analysis), we obtain $s'(n) = \Omega(n^{0.4315})$.


\section{Every $k$ points determine at least $l$ distinct distances.}\label{sec:kl}

Let $\phi(n,k,l)$ denote the minimum number of distinct distances that are determined by a planar $n$ point set $\pts$ with the property that any $k$ points of $\pts$ determine at least $l$ distinct distances (this notation is taken from \cite[Chapter 5]{BMP05}). That is, by having a local property of every small subset of points, we wish to obtain a global property of the entire point set. Table \ref{ta:secKL} lists the current best bounds for most of the problems that are discussed in this section.

\begin{table}[h]
\begin{center}
\caption{The current best bounds for some of the problems that are presented in Section \ref{sec:kl}.\label{ta:secKL}}
\vspace{2mm}

\begin{tabular}{|c|c|c|}
\hline
{\textbf {Variant}} & {\textbf {Lower bound}} & {\textbf {Upper bound}} \\
\hline\hline
$\phi(n,3,2)$  & $\Omega(n/\log n)$ \cite{GK15} & $O(n/\sqrt{\log n})$ \cite{erd46} \\ \hline
$\phi(n,3,3)$  & $\Omega(n)$ & $n2^{O(\sqrt{\log n})}$ \cite{erd86} \\ \hline
$\phi(n,4,3)$  & $\Omega(n/\log n)$ \cite{GK15} & $O(n/\sqrt{\log n})$ \\ \hline
$\phi(n,4,4)$  & $\Omega(n/\log n)$ \cite{GK15} & $n2^{O(\sqrt{\log n})}$ \cite{Dum08} \\ \hline
$\phi(n,4,5)$  & $\Omega(n)$ (trivial) & $O(n^2)$ (trivial) \\ \hline
$\phi(n,5,9)$  & $\Omega(n)$ (trivial) & $O(n^2)$ (trivial) \\ \hline
\end{tabular}
\end{center}
\vspace{-\baselineskip}
\end{table}

\noindent {\bf The case $\mathbf{\emph{k=3}}$.} The value of $\phi(n,3,2)$ is the minimum number of distinct distances that are determined by a set of $n$ points that do not span any equilateral triangles. As discussed in Section \ref{sec:structure}, Erd\H os \cite{erd46} noticed that a $\sqrt{n}\times\sqrt{n}$ integer lattice determines $\Theta(n/\sqrt{\log n})$ distinct distances. It is known that the points of the integer lattice do not determine any equilateral triangles, and thus $\phi(n,3,2)= O(n/\sqrt{\log n})$. Guth and Katz's bound on $D(n)$ \cite{GK15} implies $\phi(n,3,2)= \Omega(n/\log n)$. Thus, the current best bounds for $\phi(n,3,2)$ are identical to the ones for $D(n)$.

\begin{problem} \label{pr:n32}
Find the asymptotic value of $\phi(n,3,2)$.
\end{problem}

The value of $\phi(n,3,3)$ is the minimum number of distinct distances that are determined by a set of $n$ points that do not span any isosceles triangles (here and in the following cases, we also consider degenerate polygons, such as a degenerate isosceles triangle whose three vertices are collinear). Since no isosceles triangles are allowed, every point determines $n-1$ distinct distances with the other points of the set, and thus we have $\phi(n,3,3) = \Omega(n)$.
Erd\H os \cite{erd86} observed the following upper bound for $\phi(n,3,3)$.
Behrend \cite{Behr46} proved that there exists a set $A$ of positive integers $a_1<a_2<\cdots<a_n$, such that no three elements of $A$ determine an arithmetic progression and that $a_n < n2^{O(\sqrt{\log n})}$.
Therefore, the point set $\pts_1 = \{(a_1,0), (a_2,0),\ldots, (a_n,0)\} \subset \RR^2$ does not span any isosceles triangles. Since $\pts_1 \subset \pts_2 = \{(1,0),(2,0),\ldots,(a_n,0) \}$ and $D(\pts_2)< n2^{O(\sqrt{\log n})}$, we have $\phi(n,3,3) < n2^{O(\sqrt{\log n})}$.
Erd\H os conjectured \cite{erd86} that $\phi(n,3,3) = \omega(n)$.

\begin{problem} \label{pr:n33}
Find the asymptotic value of $\phi(n,3,3)$.
\end{problem}

\noindent {\bf The case $\mathbf{\emph{k=4}}$.} The value of $\phi(n,4,3)$ is the minimum number of distinct distances that are determined by a set of $n$ points that do not span any squares. This case is somewhat similar to the one of $\phi(n,3,2)$. The $\sqrt{n}\times\sqrt{n}$ triangular lattice determines $\Theta(n/\sqrt{\log n})$ distinct distances (e.g., see \cite{Sblog14}). Since the triangular lattice does not contain any squares, we have $\phi(n,4,3) = O(n/\sqrt{\log n})$. The current best lower bound $\phi(n,4,3) = \Omega(n/\log n)$ is Guth and Katz's general bound.

\begin{problem} \label{pr:n43}
Find the asymptotic value of $\phi(n,4,3)$.
\end{problem}


\begin{figure}[h]

\centerline{\placefig{deltoid}{0.6\textwidth}}
\vspace{-1mm}

\caption{\small \sf (a) The point $p$ is equidistant from the other three vertices of the deltoid. (b) The only possible cases of segments having the same length are $|ab|=|cd|$ and $|ac|=|bd|$.}
\label{fi:deltoid}
\vspace{-2mm}
\end{figure}

The value of $\phi(n,4,4)$ is the minimum number of distinct distances that are determined by a set of $n$ points that do not span any rhombuses, rectangles, or deltoids with one vertex that is equidistant to the three other three (see Figure \ref{fi:deltoid}(a)). Dumitrescu \cite{Dum08} observed that $\phi(n,4,4)< n2^{O(\sqrt{\log n})}$ by using the same point set $\pts_1$ from the analysis of $\phi(n,3,3)$. Indeed, consider a subset of four points of $\pts_1$, as depicted in Figure \ref{fi:deltoid}(b), and notice that the only pairs of segments that are allowed to have the same length (without resulting in an arithmetic progression) are $|ab|=|cd|$ and $|ac|=|bd|$. Thus, every quadruple of points determines at least four distinct distances.
No lower bound is known beyond $\phi(n,4,4)=\Omega(n/\log n)$.

\begin{problem} \label{pr:n44}
Find the asymptotic value of $\phi(n,4,4)$.
\end{problem}

Not much is known about the case of $\phi(n,4,5)$. Erd\H os \cite{erd86} asked whether $\phi(n,4,5)=\Theta(n^2)$, though the current best lower bound is only $\phi(n,4,5)= \Omega(n)$.
Indeed, when considering an $n$ point set $\pts$ with this property, we notice that any circle whose center is a point of $\pts$ can be incident to at most two points of $\pts$.

\begin{problem} \label{pr:n45}
Find the asymptotic value of $\phi(n,4,5)$.
\end{problem}


Finally, we have the trivial bound $\phi(n,4,6) = n(n-1)/2$, since every distance can occur at most once in this case.

\noindent {\bf The case $\mathbf{\emph{k=5}}$.} We do not go over the various cases of $k=5$, and only mention that Erd\H os \cite{erd86} asked whether $\phi(n,5,9)=\Omega(n^2)$. Again, nothing is known in this case beyond the trivial $\phi(n,5,9)=\Omega(n)$.

\begin{problem} \label{pr:n59}
Find the asymptotic value of $\phi(n,5,9)$.
\end{problem}

\noindent {\bf The general case.} Erd\H os \cite{erd86} noticed that, for any $k\ge 3$, we have
%
\[\phi\left(n,k,\binom{k}{2}-k+3\right) = \Omega(n). \]
%
To see why, consider a set $\pts$ of $n$ points such that every $k$-point subset of $\pts$ determines at least $\binom{k}{2}-k+3$ distinct distances, and a point $p\in\pts$. If $p$ is the center of a circle that is incident to $k-1$ points of $\pts$, then together these $k$ points determine at most $\binom{k}{2}-k+2$ distinct distances, contradicting the assumption on $\pts$. Thus, the points of $\pts\setminus \{p\}$ are contained in at least $(n-1)/(k-2)$ circles around $p$, which in turn implies that $p$ determines $\Omega(n)$ distinct distances with the other points of $\pts$.

Another simple observation is that, for any $k\ge 4$, we have
%
\[ \phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +2 \right) = \Omega(n^2), \]
%
since in this case every distance can occur at most $\lfloor k/2 \rfloor -1$ times.

Similarly to the cases of $\phi(n,3,3)$ and $\phi(n,4,4)$, we can use the set $\pts_1$ to obtain a bound of $n2^{O(\sqrt{\log n})}$ for various $\phi(n,k,l)$. For example, it is not hard to show that %
\[\phi\left(n,k,2\lfloor k/2 \rfloor\right)=n2^{O(\sqrt{\log n})}. \]
%
It seems likely that a more careful analysis would yield the same bound for larger values of $l$.

\begin{problem} \label{pr:nkl}
Find stronger general bounds for $\phi(n,k,l)$.
\end{problem}


\section{Additional problems} \label{sec:additional}
In this section we discuss problems that did not fit into any of the previous sections.

In Problems \ref{pr:lines}, \ref{pr:curves}, and \ref{pr:surfs}, we considered bipartite distinct distances problems, where we have two sets of points $\pts_1$ and $\pts_2$, and are interested only in distinct distances that are spanned by pairs of $\pts_1\times\pts_2$ (i.e., distances between points from different sets). We now consider a somewhat different bipartite problem, where  $\pts_1$ is a set of three points and $\pts_2$ is a set of $n$ points, both in $\RR^2$. A simple argument shows that the number of distinct distances between two such sets is $\Omega(n^{1/2})$. Elekes \cite{Elek95} constructed a configuration where the three points of $\pts_1$ are evenly spaced on a line, and the number of distinct distances between the two sets is $\Theta(n^{1/2})$, thus settling this problem.

We denote by $D(3,n)$ the minimum number of distinct distances between a set $\pts_1$ of three \emph{non-collinear} points and a set $\pts_2$ of $n$ points.
Elekes and Szab\'o \cite{ES12} proved the bound $D(3,n)=\Omega(n^{0.502})$, showing that collinearity is necessary for obtaining a bound of $\Theta(n^{1/2})$. Recently, Sharir and Solymosi \cite{SSo13} obtained a more significant improvement, proving $D(3,n)=\Omega(n^{6/11})$. The current best upper bound is the trivial $D(3,n)= (n/\sqrt{\log n})$.

\begin{problem}
Find the asymptotic value of $D(3,n)$.
\end{problem}

Another bipartite variant was recently suggested by Sharir, Smorodinsky, Valculescu, and de Zeeuw \cite{SSmo14}.
Denote by $L(m,n)$ the minimum number of distinct distances between a set of $m$ points and a set of $n$ \emph{lines}, both in $\RR^2$ (where the distance between a point and a line is defined in the usual way).
By placing $m$ points on a line $\ell$ and then taking $n$ lines that are parallel to $\ell$, we obtain  $L(m,n) = O(n)$. When $\sqrt{m}< n <m^2$, the bound $L(m,n) = \Omega( m^{1/5} n^{3/5} )$ was derived in \cite{SSmo14}.

\begin{problem}
Find the asymptotic value of $L(m,n)$.
\end{problem}

We next consider a variant of Problem \ref{pr:mainPnt}. Given a planar point set $\pts$ and a point $p \in\pts$, we denote by $\hd_p(\pts)$ the number of distinct distances between $p$ and the other points of $\pts$. We set $\hd_\Sigma(\pts)=\sum_{p\in\pts}\hd_p(\pts)$ and $\hd_\Sigma(n) = \min_{|\pts|=n}\hd_\Sigma(\pts)$. It is not hard to verify that if $\pts$ is a $\sqrt{n}\times\sqrt{n}$ integer lattice, then $\hd_\Sigma(\pts) = \Theta\left(n^2/\sqrt{\log n}\right)$. Erd\H os conjectured \cite{Erd75,erd87} that this should also be the value of $\hd_\Sigma(n)$.

\begin{problem}
Find the asymptotic value of $\hd_\Sigma(n)$.
\end{problem}
%
The current best lower bound $\hd_\Sigma(n) = \Omega(n^{1.864})$ is immediately implied by Katz and Tardos' \cite{KT04} bound $\hd(n) = \Omega(n^{(48-14e)/(55-16e)})\approx \Omega(n^{0.864})$ (by repeatedly removing a point $p$ that maximizes $\hd_p(\pts)$).

Next, we consider a generalization from distinct distances to \emph{distinct vectors}. Given a planar point set $\pts$, we denote by $v(\pts)$ the number of distinct vectors that are spanned by pairs of points of $\pts$ (i.e., the points $p,q$ span the vectors $p-q$ and $q-p$), and set $v(n) = \min_{|\pts|=n}v(\pts)$. Clearly, $v(n)$ should be at least as large as $D(n)$. In fact, it is also not hard to show that $v(n) = \Theta(n)$. Indeed, the $\sqrt{n}\times\sqrt{n}$ integer lattice determines $\Theta(n)$ distinct vectors.

Erd\H os, F\"uredi, Pach, and Ruzsa \cite{EFPR93} studied the case of distinct vectors for point sets in general position (i.e., no three points on a line and no four points on a circle). We set $v_\text{gen}(n) = \min_{|\pts|=n}v(\pts)$, where the sum is taken over every set of $n$ points in general position. In \cite{EFPR93}, it is proven that $v_\text{gen}(n) > cn$ for \emph{every} constant $c$; i.e., $v_\text{gen}(n) =\omega(n)$. The current best upper bound  $v_\text{gen}(n) = n2^{O(\log n)}$ is immediately implied by the current best upper bound for Problem \ref{pr:gen}.

\begin{problem}
Find the asymptotic value of $v_\text{gen}(n)$.
\end{problem}
%
\vspace{3mm}


\noindent {\bf Acknowledgements.} The author is indebted to the various people who helped improve this survey. These are Adrian Dumitrescu, William Gasarch, Ben Lund, Micha Sharir, and Frank de Zeeuw.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}
%
\bibitem{Alt63}
E.\ Altman,
On a problem of P.\ Erd\H os,
\emph{Amer.\ Math.\ Monthly} {\bf 70} (1963), 148--157.
%
\bibitem{Alt72}
E.\ Altman,
Some theorems on convex polygons,
\emph{Canad.\ Math.\ Bull.} {\bf 15} (1972), 329--340.
%
\bibitem{Behr46}
F.\ A.\ Behrend,
On sets of integers which contain no three terms in arithmetic progression,
\emph{Proc.\ Nat.\ Acad.\ Sci.} {\bf 32} (1946), 331--332.
%
\bibitem{BR95}
B.\ C.\ Berndt and R.\ A.\ Rankin,
\emph{Ramanujan: Letters and Commentary},
Amer. Math. Soc., Providence, RI, 1995.
%
\bibitem{BMP05}
P.\ Brass, W.\ Moser, and J.\ Pach,
\emph{Research Problems in Discrete Geometry},
Springer-Verlag, New York, 2005.
%
\bibitem{BMO11}
D.\ Brink, P.\ Moree, and R.\ Osburn,
Principal forms $X^2 + nY^2$ representing many integers,
\emph{Abh.\ Math.\ Sem.\ Univ.\ Hambg.}, {\bf 81} (2011), 129--139.
%
\bibitem{Chara12}
M.\ Charalambides,
A note on distinct distance subsets,
\emph{Journal of Geometry}, {\bf 104} (2013), 439--442.
%
\bibitem{Chara13}
M.\ Charalambides,
Exponent gaps on curves via rigidity,
arXiv:1307.0870.
%
\bibitem{CFGHUZ14}
D.\ Conlon, J.\ Fox, W.\ Gasarch, D.\ Harris, D.\ Ulrich, and S.\ Zbarsky,
Distinct volume subsets,
arXiv:1401.6734.
%
\bibitem{Dum06}
A.\ Dumitrescu,
On distinct distances from a vertex of a convex polygon,
\emph{Discrete Comput. Geom.} {\bf 36}(4) (2006), 503--509.
%
\bibitem{Dum08}
A.\ Dumitrescu, On distinct distances among points in general position and other related problems,
\emph{Periodica Mathematica Hungarica} {\bf 57}(2) (2008), 165--176.
%
\bibitem{Elek95}
G.\ Elekes,
Circle grids and bipartite graphs of distances,
\emph{Combinatorica} {\bf 15} (1995), 167--174.
%
\bibitem{Elek99}
G.\ Elekes,
A note on the number of distinct distances,
\emph{Period.\ Math.\ Hung.}, {\bf 38} (1999), 173--177.
%
\bibitem{ER00}
G.\ Elekes and L.\ R\'onyai, A combinatorial problem on polynomials and
rational functions,
\emph{J.\ Combin.\ Theory Ser.\ A}, {\bf 89} (2000), 1--20.
%
\bibitem{ES12}
G.\ Elekes and E.\ Szab\'o,
How to ﬁnd groups? (and how to use them in Erd˝os geometry?),
\emph{Combinatorica} {\bf 32} (2012), 537--571.
%
\bibitem{erd46}
P.\ Erd\H os,
On sets of distances of $n$ points,
\emph{Amer. Math. Monthly} {\bf 53} (1946), 248--250.
%
\bibitem{Erd57}
P.\ Erd\H os, Nehany geometriai probl\'em\'ar\'ol (in Hungarian), \emph{Matematikai Lapok}, {\bf 8} (1957), 86--92.
%
\bibitem{Erd75}
P.\ Erd\H os,
On some problems of elementary and combinatorial geometry,
\emph{Ann.\ Mat.\ Pura Appl.} {\bf 103} (1975), 99--108.
%
\bibitem{erd86}
P.\ Erd\H os,
On some metric and combinatorial geometric problems,
\emph{Discrete Math.} {\bf 60} (1986), 147--153.
%
\bibitem{erd87}
P.\ Erd\H os,
Some combinatorial and metric problems in geometry,
\emph{Intuitive geometry} (K.\ B\"or\"oczky and G.\ Fejes T\`oth, eds.), North-Holland, Amsterdam-New York, 1987, 167--177.
%
\bibitem{erd96}
P.\ Erd\H os,
On some of my favourite theorems,
\emph{Combinatorics, Paul Erd\H os is Eighty,}
Vol. 2 (D. Mikl\'os et al., eds.), Bolyai Society Mathematical Studies 2, Budapest, 1996,
97--132.
%
\bibitem{EF96}
P.\ Erd\H os and P.\ Fishburn,
Maximum planar sets that determine $k$ distances,
\emph{Discrete Math.} {\bf 160} (1996), 115--125.
%
\bibitem{EFPR93}
P.\ Erd\H os, Z.\ F\"uredi, J.\ Pach, and I.\ Z.\ Ruzsa,
The grid revisited,
\emph{Discrete Math.} {\bf 111} (1993), 189--196.
%
\bibitem{EG70}
P.\ Erd\H os, R.\ K.\ Guy,
Distinct distances between lattice points,
\emph{Elemente Math.} {\bf 25} (1970) 121--123.
%
\bibitem{EHP89}
P.\ Erd\H os, D.\ Hickerson, and J.\ Pach,
A problem of Leo Moser about repeated distances on the sphere,
\emph{Amer.\ Math.\ Monthly} {\bf 96} (1989), 569--575.
%
\bibitem{EP95}
P.\ Erd\H os and G.\ Purdy,
Extremal problems in combinatorial geometry,
\emph{Handbook of Combinatorics},
Vol. I (R.\ L.\ Graham, M.\ Gr\H otschel, and L. Lov\'asz, editors), Elsevier, Amsterdam, 1995, pp. 809--
874.
%
\bibitem{GIS11}	
J.\ Garibaldi, A.\ Iosevich, and S.\ Senger,
\emph{The Erd{\H o}s Distance Problem},
Student Math. Library, Vol. 56,
Amer. Math. Soc. Press, Providence, RI, 2011.
%
\bibitem{GK15}	
L.\ Guth and N.\ H.\ Katz,
On the Erd{\H o}s distinct distances problem in the plane,
{\em Annals of Mathematics}, {\bf 181} (2015), 155--190.
%
\bibitem{KT04}
N.\ H.\ Katz and G.\ Tardos,
A new entropy inequality for the Erd\H os distance problem,
\emph{Towards a Theory of Geometric Graphs (J. Pach, ed.)}, Contemporary Mathematics {\bf 342}, AMS, Providence, RI, 2004, 119--126.
%
\bibitem{Land08}
E.\ Landau,
\"Uber die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindeszahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate,
\emph{Arch.\ Math.\ Phys.} {\bf 13} (1908), 305--312.
%
\bibitem{LT95}
H.\ Lefmann and T.\ Thiele,
Point sets with distinct distances,
\emph{Combinatorica} {\bf 15} (1995) 379--408.
%
\bibitem{LSdZ15}
B.\ Lund, A.\ Sheffer, and F.\ de Zeeuw,
Bisector energy and few distinct distances,
arXiv:1411.6868.
%
\bibitem{NPPZ11}
G.\ Nivasch, J.\ Pach, R.\ Pinchasi, and S.\ Zerbib,
The number of distinct distances from a vertex of a convex polygon,
\emph{J.\ Computational Geometry}, {\bf 4} (2013), 1--12.
%
\bibitem{PA95}
J.\ Pach and P.\ K.\ Agarwal,
\emph{Combinatorial Geometry}, Wiley-Interscience, New York, 1995.
%
\bibitem{PZ13}
J.\ Pach and F.\ de Zeeuw
Distinct Distances on Algebraic Curves in the Plane,
\emph{Proc.\ 30th ACM Symp.\ on Computational Geometry} (2014), 549--557.
%
\bibitem{PT02}
J.\ Pach and G.\ Tardos,
Isosceles triangles determined by a planar point set,
\emph{Graphs and Combinatorics} {\bf 18} (2002), 769--779.
%
\bibitem{RRNS15}
O.\ E.\ Raz, O.\ Roche-Newton, and M.\ Sharir,
Sets with few distinct distances do not have heavy lines,
\emph{Discrete Math.} {\bf 338} (2015), 1484--1492.
%
\bibitem{RSS14}
O.\ E.\ Raz, M.\ Sharir and J.\ Solymosi,
Polynomials vanishing on grids: The Elekes-R\'onyai problem revisited,
\emph{Amer. J. Math.}, to appear.
%
\bibitem{SSZ12}
R.\ Schwartz, J.\ Solymosi, and F.\ de Zeeuw,
Extensions of a result of Elekes and R\'onyai,
\emph{J.\ Combin.\ Theory Ser.\ A}, {\bf 120} (2013), 1695--1713.
%
\bibitem{SS13}
M.\ Sharir, A.\ Sheffer, and J.\ Solymosi,
Distinct distances on two lines,
J. Combinat. Theory A, 120 (2013), 1732--1736.
%
\bibitem{SSmo14}
M.\ Sharir, S.\ Smorodinsky, C.\ Valculescu, and F.\ de Zeeuw,
On Distinct Distances Between Points and Lines,
Manuscript.
%
\bibitem{SSo13}
M.\ Sharir and J.\ Solymosi,
Distinct distances from three points,
\emph{Combinat. Probab. Comput.}, to appear.
%
\bibitem{Sblog14}
A.\ Sheffer,
Point Sets with Few Distinct Distances, blog post,
\url{https://adamsheffer.wordpress.com/2014/07/16/point-sets-with-few-distinct-distances/}
%
\bibitem{Sblog14b}
A.\ Sheffer,
Few Distinct Distances Implies Many Points on a Line, blog post,
\url{https://adamsheffer.wordpress.com/2014/10/07/few-distinct-distances-implies-many-points-on-a-line/}
%
\bibitem{SZZ13}
A.\ Sheffer, J.\ Zahl, and F.\ de Zeeuw,
Few distinct distances implies no heavy lines or circles,
\emph{Combinatorica}, to appear.
%
\bibitem{SV08}
J.\ Solymosi and V.\ H.\ Vu,
Near optimal bounds for the Erd\H os distinct distances problem in high dimensions.
\emph{Combinatorica} {\bf 28}(1) (2008), 113--125.
%
\bibitem{Tao11}
T.\ Tao,
Lines in the Euclidean group SE(2),
blog post, \url{http://terrytao.wordpress.com/2011/03/05/lines-in-the-euclidean-group-se2/}
%
\bibitem{Thiele95}
T.\ Thiele,
\emph{Geometric selection problems and hypergraphs}, PhD thesis, Instut fur
Mathematik II Freir Universitat Berlin, 1995.
%
\end{thebibliography}

\end{document}


1406.1949.extracted_bib
{Alt63 E.\ Altman, On a problem of P.\ Erd\H os, Amer.\ Math.\ Monthly {70 (1963), 148--157. %
1406.1949.extracted_bib
{Alt72 E.\ Altman, Some theorems on convex polygons, Canad.\ Math.\ Bull. {15 (1972), 329--340. %
1406.1949.extracted_bib
{Behr46 F.\ A.\ Behrend, On sets of integers which contain no three terms in arithmetic progression, Proc.\ Nat.\ Acad.\ Sci. {32 (1946), 331--332. %
1406.1949.extracted_bib
{BR95 B.\ C.\ Berndt and R.\ A.\ Rankin, Ramanujan: Letters and Commentary, Amer. Math. Soc., Providence, RI, 1995. %
1406.1949.extracted_bib
{BMP05 P.\ Brass, W.\ Moser, and J.\ Pach, Research Problems in Discrete Geometry, Springer-Verlag, New York, 2005. %
1406.1949.extracted_bib
{BMO11 D.\ Brink, P.\ Moree, and R.\ Osburn, Principal forms $X^2 + nY^2$ representing many integers, Abh.\ Math.\ Sem.\ Univ.\ Hambg., {81 (2011), 129--139. %
1406.1949.extracted_bib
{Chara12 M.\ Charalambides, A note on distinct distance subsets, Journal of Geometry, {104 (2013), 439--442. %
1406.1949.extracted_bib
{Chara13 M.\ Charalambides, Exponent gaps on curves via rigidity, arXiv:1307.0870. %
1406.1949.extracted_bib
{CFGHUZ14 D.\ Conlon, J.\ Fox, W.\ Gasarch, D.\ Harris, D.\ Ulrich, and S.\ Zbarsky, Distinct volume subsets, arXiv:1401.6734. %
1406.1949.extracted_bib
{Dum06 A.\ Dumitrescu, On distinct distances from a vertex of a convex polygon, Discrete Comput. Geom. {36(4) (2006), 503--509. %
1406.1949.extracted_bib
{Dum08 A.\ Dumitrescu, On distinct distances among points in general position and other related problems, Periodica Mathematica Hungarica {57(2) (2008), 165--176. %
1406.1949.extracted_bib
{Elek95 G.\ Elekes, Circle grids and bipartite graphs of distances, Combinatorica {15 (1995), 167--174. %
1406.1949.extracted_bib
{Elek99 G.\ Elekes, A note on the number of distinct distances, Period.\ Math.\ Hung., {38 (1999), 173--177. %
1406.1949.extracted_bib
{ER00 G.\ Elekes and L.\ R\'onyai, A combinatorial problem on polynomials and rational functions, J.\ Combin.\ Theory Ser.\ A, {89 (2000), 1--20. %
1406.1949.extracted_bib
{ES12 G.\ Elekes and E.\ Szab\'o, How to ﬁnd groups? (and how to use them in Erd˝os geometry?), Combinatorica {32 (2012), 537--571. %
1406.1949.extracted_bib
{erd46 P.\ Erd\H os, On sets of distances of $n$ points, Amer. Math. Monthly {53 (1946), 248--250. %
1406.1949.extracted_bib
{Erd57 P.\ Erd\H os, Nehany geometriai probl\'em\'ar\'ol (in Hungarian), Matematikai Lapok, {8 (1957), 86--92. %
1406.1949.extracted_bib
{Erd75 P.\ Erd\H os, On some problems of elementary and combinatorial geometry, Ann.\ Mat.\ Pura Appl. {103 (1975), 99--108. %
1406.1949.extracted_bib
{erd86 P.\ Erd\H os, On some metric and combinatorial geometric problems, Discrete Math. {60 (1986), 147--153. %
1406.1949.extracted_bib
{erd87 P.\ Erd\H os, Some combinatorial and metric problems in geometry, Intuitive geometry (K.\ B\"or\"oczky and G.\ Fejes T\`oth, eds.), North-Holland, Amsterdam-New York, 1987, 167--177. %
1406.1949.extracted_bib
{erd96 P.\ Erd\H os, On some of my favourite theorems, Combinatorics, Paul Erd\H os is Eighty, Vol. 2 (D. Mikl\'os et al., eds.), Bolyai Society Mathematical Studies 2, Budapest, 1996, 97--132. %
1406.1949.extracted_bib
{EF96 P.\ Erd\H os and P.\ Fishburn, Maximum planar sets that determine $k$ distances, Discrete Math. {160 (1996), 115--125. %
1406.1949.extracted_bib
{EFPR93 P.\ Erd\H os, Z.\ F\"uredi, J.\ Pach, and I.\ Z.\ Ruzsa, The grid revisited, Discrete Math. {111 (1993), 189--196. %
1406.1949.extracted_bib
{EG70 P.\ Erd\H os, R.\ K.\ Guy, Distinct distances between lattice points, Elemente Math. {25 (1970) 121--123. %
1406.1949.extracted_bib
{EHP89 P.\ Erd\H os, D.\ Hickerson, and J.\ Pach, A problem of Leo Moser about repeated distances on the sphere, Amer.\ Math.\ Monthly {96 (1989), 569--575. %
1406.1949.extracted_bib
{EP95 P.\ Erd\H os and G.\ Purdy, Extremal problems in combinatorial geometry, Handbook of Combinatorics, Vol. I (R.\ L.\ Graham, M.\ Gr\H otschel, and L. Lov\'asz, editors), Elsevier, Amsterdam, 1995, pp. 809-- 874. %
1406.1949.extracted_bib
{GIS11 J.\ Garibaldi, A.\ Iosevich, and S.\ Senger, The Erd{\H os Distance Problem, Student Math. Library, Vol. 56, Amer. Math. Soc. Press, Providence, RI, 2011. %
1406.1949.extracted_bib
{GK15 L.\ Guth and N.\ H.\ Katz, On the Erd{\H os distinct distances problem in the plane, {\em Annals of Mathematics, {181 (2015), 155--190. %
1406.1949.extracted_bib
{KT04 N.\ H.\ Katz and G.\ Tardos, A new entropy inequality for the Erd\H os distance problem, Towards a Theory of Geometric Graphs (J. Pach, ed.), Contemporary Mathematics {342, AMS, Providence, RI, 2004, 119--126. %
1406.1949.extracted_bib
{Land08 E.\ Landau, \"Uber die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindeszahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate, Arch.\ Math.\ Phys. {13 (1908), 305--312. %
1406.1949.extracted_bib
{LT95 H.\ Lefmann and T.\ Thiele, Point sets with distinct distances, Combinatorica {15 (1995) 379--408. %
1406.1949.extracted_bib
{LSdZ15 B.\ Lund, A.\ Sheffer, and F.\ de Zeeuw, Bisector energy and few distinct distances, arXiv:1411.6868. %
1406.1949.extracted_bib
{NPPZ11 G.\ Nivasch, J.\ Pach, R.\ Pinchasi, and S.\ Zerbib, The number of distinct distances from a vertex of a convex polygon, J.\ Computational Geometry, {4 (2013), 1--12. %
1406.1949.extracted_bib
{PA95 J.\ Pach and P.\ K.\ Agarwal, Combinatorial Geometry, Wiley-Interscience, New York, 1995. %
1406.1949.extracted_bib
{PZ13 J.\ Pach and F.\ de Zeeuw Distinct Distances on Algebraic Curves in the Plane, Proc.\ 30th ACM Symp.\ on Computational Geometry (2014), 549--557. %
1406.1949.extracted_bib
{PT02 J.\ Pach and G.\ Tardos, Isosceles triangles determined by a planar point set, Graphs and Combinatorics {18 (2002), 769--779. %
1406.1949.extracted_bib
{RRNS15 O.\ E.\ Raz, O.\ Roche-Newton, and M.\ Sharir, Sets with few distinct distances do not have heavy lines, Discrete Math. {338 (2015), 1484--1492. %
1406.1949.extracted_bib
{RSS14 O.\ E.\ Raz, M.\ Sharir and J.\ Solymosi, Polynomials vanishing on grids: The Elekes-R\'onyai problem revisited, Amer. J. Math., to appear. %
1406.1949.extracted_bib
{SSZ12 R.\ Schwartz, J.\ Solymosi, and F.\ de Zeeuw, Extensions of a result of Elekes and R\'onyai, J.\ Combin.\ Theory Ser.\ A, {120 (2013), 1695--1713. %
1406.1949.extracted_bib
{SS13 M.\ Sharir, A.\ Sheffer, and J.\ Solymosi, Distinct distances on two lines, J. Combinat. Theory A, 120 (2013), 1732--1736. %
1406.1949.extracted_bib
{SSmo14 M.\ Sharir, S.\ Smorodinsky, C.\ Valculescu, and F.\ de Zeeuw, On Distinct Distances Between Points and Lines, Manuscript. %
1406.1949.extracted_bib
{SSo13 M.\ Sharir and J.\ Solymosi, Distinct distances from three points, Combinat. Probab. Comput., to appear. %
1406.1949.extracted_bib
{Sblog14 A.\ Sheffer, Point Sets with Few Distinct Distances, blog post, \url{https://adamsheffer.wordpress.com/2014/07/16/point-sets-with-few-distinct-distances/ %
1406.1949.extracted_bib
{Sblog14b A.\ Sheffer, Few Distinct Distances Implies Many Points on a Line, blog post, \url{https://adamsheffer.wordpress.com/2014/10/07/few-distinct-distances-implies-many-points-on-a-line/ %
1406.1949.extracted_bib
{SZZ13 A.\ Sheffer, J.\ Zahl, and F.\ de Zeeuw, Few distinct distances implies no heavy lines or circles, Combinatorica, to appear. %
1406.1949.extracted_bib
{SV08 J.\ Solymosi and V.\ H.\ Vu, Near optimal bounds for the Erd\H os distinct distances problem in high dimensions. Combinatorica {28(1) (2008), 113--125. %
1406.1949.extracted_bib
{Tao11 T.\ Tao, Lines in the Euclidean group SE(2), blog post, \url{http://terrytao.wordpress.com/2011/03/05/lines-in-the-euclidean-group-se2/ %
1406.1949.extracted_bib
{Thiele95 T.\ Thiele, Geometric selection problems and hypergraphs, PhD thesis, Instut fur Mathematik II Freir Universitat Berlin, 1995. %