On point sets with many unit distances in few directions (Q1387845)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On point sets with many unit distances in few directions |
scientific article |
Statements
On point sets with many unit distances in few directions (English)
0 references
14 June 1999
0 references
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\)).
0 references
unit distances
0 references
unit distance graphs
0 references