Given N and d, what's the maximal line segments with length d in plane with N points.

Question

Given $N$ and $d$, what's the maximal number of line segments of length $d$ in plane with $N$ points.

I have a hypothesis, it is $\Theta(N)$, but I can't figure out, how to prove or contradict it.

Thanks for your help.

Edit:

Let's have result $f(N)$. $f(N)\in\Theta(N)$ means that there are $c_1, c_2, k\in \mathbb{R}$ such that $c_1 N \leq f(N)\leq c_2 N$ for every $N>k$.

I would be happy with even with just asymtotic solution.

Answer 1

By rescaling, you may as well assume $d=1$. In this form this is an old open problem known as the "Erdős Unit Distance Problem". Erdős showed in 1946 that the maximum is at least $n^{1+c/\log \log n}$ (in particular, that it's not linear), but the corresponding best known upper bound is only on the order of $n^{4/3}$. Szemerédi (who proved this upper bound together with Spencer and Trotter) has a recent survey of work on the problem.