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

From MaRDI portal
Revision as of 10:34, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references