Minimal number of points on a grid forming line segments of equal length

Abstract

We consider the minimal number of points on a regular grid on the plane that generates $n$ line segments of points of exactly length $k$. We illustrate how this is related to the $n$-queens problem on the toroidal chessboard and show that this number is upper bounded by $kn/3$ and approaches $kn/4$ as $n\to \infty$ when $k+1$ is coprime with $6$ or when $k$ is large.

arXiv comment9 pages, 6 figures