On point sets with many unit distances in few directions (Q1387845)

The author studies the problem of the maximum number \(f(n,k)\) of unit distances among \(n\) points in the plane, under the additional restriction that only those unit distances are counted that occur in a fixed set of \(k\) directions, taking the maximum over all sets of \(n\) points and all sets of \(k\) directions. The case \(k=1\) is trivial, and in the case \(k=2\) it is sufficient to consider subgraphs of the square lattice graph. In this way, \textit{F. Harary} and \textit{H. Harborth} [J. Comb. Inf. Syst. Sci. 1, 1-8 (1976; Zbl 0402.05055)] found \(f(n,2)=\lfloor 2n-2\sqrt{n}\rfloor \). Here the author shows \(f(n,k)=kn-O( \sqrt{n})\) for arbitrary \(k\) and determines the extremal sets of points and directions for sufficiently large \(n>n_0(k)\) and fixed \(k\geq 3\). It turns out that the extremal set is, with the exception of at most \(O\left( \sqrt{n}\right) \) points, a section of a lattice which is bounded by edges parallel to the given directions. (A point set \(S\subset \Gamma \) is called a section of a lattice \(\Gamma \) if there is a convex set \(K\) such that all points of \(\Gamma \) that are in the interior of \(K\) belong to \(S\), and all points of \(\Gamma \) that are in the exterior of \(K\) do not belong to \(S\). There is no assumption on the lattice points on the boundary of \(K\)).