2014/06/23 by Mark Herman, Herman, Mark, Jonathan Pakianathan +1
Computer Science · Mathematics · #52C10 Secondary: 05C35 #52C35 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Approximation and Integration #Metric Geometry (math.MG) #Point processes and geometric inequalities #Primary: 05D99 #math.CO #math.MG #msc:05C35 #msc:05D99 #msc:52C10 #msc:52C35
paper · pdf · doi:10.48550/arxiv.1406.6029
19 pages
openalex publication_date 2014/06/23 · arxiv created 2014/06/25 · arxiv updated 2014/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let T(n) denote the maximum number of unit distances that a set of n points in the Euclidean plane ℝ2 can determine with the additional condition that the distinct unit length directions determined by the configuration must be ℚ-independent. This is related to the Erdos unit distance problem but with a simplifying additional assumption on the direction set which holds "generically". We show that T(n+1)-T(n) is the Hamming weight of n, i.e., the number of nonzero binary coefficients in the binary expansion of n, and find a formula for T(n) explicitly. In particular T(n) is Θ(n log(n)). Furthermore we describe a process to construct a set of n points in the plane with ℚ-independent unit length direction set which achieves exactly T(n) unit distances. In the process of doing this, we show T(n) is also the same as the maximum number of edges a subset of vertices of size n determines in either the countably infinite lattice ℤ∞ or the infinite hypercube graph \0,1\∞. The problem of determining T(n) can be viewed as either a type of packing or isoperimetric problem.