On point sets with many unit distances in few directions
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\)).
- The additive structure of Cartesian products spanning few distinct distances
- Unit distances
- Maximum planar sets that determine k distances
- scientific article; zbMATH DE number 1234826
- A note on the unit distance problem for planar configurations with \(\mathbb{Q}\)-independent direction set
- scientific article; zbMATH DE number 4019892
- On some metric and combinatorial geometric problems
- Circle grids and bipartite graphs of distances
- scientific article; zbMATH DE number 1440118
- The multiplicity of the two smallest distances among points
- Point sets with many unit circles
- A class of point-sets with few k-sets
- Multiple coverings of the farthest-off points with small density from projective geometry
- Few cuts meet many point sets
- Isoperimetrically optimal polygons in the triangular grid with Jordan-type neighbourhood on the boundary
- Isoperimetrically optimal polygons in the triangular grid
- scientific article; zbMATH DE number 3153711 (Why is no real title available?)
- Extreme Distances in Multicolored Point Sets
- A note on the unit distance problem for planar configurations with \(\mathbb{Q}\)-independent direction set
- Additive structure in convex translates
This page was built for publication: On point sets with many unit distances in few directions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1387845)
