# Distinct Distances for Sets with no Repeated Bisectors

This post is about a distinct distances problem which I think is quite interesting. As we shall see, solving this problem would also lead to significant progress in characterizing point sets with a small number of distinct distances. Recall that a perpendicular bisector of two points $p,q\in {\mathbb R}^2$ is the line that consists of the points $a$ satisfying $|pa|=|qa|$ (where $|pa|$ is the distance between $a$ and $p$). For brevity, we will simply refer to these as bisectors.

We say that a set ${\cal P}$ of $n$ points in ${\mathbb R}^2$ has no repeated bisectors if for every four distinct points $a,b,c,d\in {\cal P}$ the bisector of $a$ and $b$ is not identical to the bisector of $c$ and $d$ (that is, the configuration in the above figure is forbidden).

Conjecture. Let ${\cal P}$ be a set of $n$ points in ${\mathbb R}^2$ with no repeated bisectors. Then for any $\varepsilon>0$ the points of ${\cal P}$ determine $\Omega(n^{2-\varepsilon})$ distinct distances, .

Update July 2017: The conjecture is false, as pointed out by Cosmin Pohoata. A known construction is a counterexample, and I should be ashamed for not observing this on my own. Erdős, Füredi, Pach, and Ruzsa constructed a set of $n$ points in ${\mathbb R}^2$ with $O(n^{1+\varepsilon})$ distinct distances for any $\varepsilon >0$ and no four points on a common circle. Having a repeated bisector requires having four points on a circle, so there are no repeated bisectors. Oh well…

For some initial intuition, consider the point sets that determine a small number of distinct distances. I am only aware of two types of configurations that yield $O(n)$ distinct distances: the vertices of a regular $n$-gon and lattices.

We can also play a bit with these examples. For example, by taking two regular $n$-gons whose vertices are on two concentric circles, or by taking $n$ evenly spaced points on a line (that is, an $n\times 1$ lattice). All of these examples have a significantly large amount of repeated bisectors.

So far I only managed to find a set with no repeated bisectors and $O(\frac{n^2}{\sqrt{\lg n}})$ distinct distances. From the other direction, I can only show that every such set determines $\Omega(n)$ distinct distances. This is unfortunate, since a stronger bound for this problem would lead to a breakthrough in characterizing planar point sets that determine a small number of distinct distances. Below I describe how this can be done, and also how to obtain simple lower and upper bounds for this problem.