A note on the unit distance problem for planar configurations with $\mathbb{Q}$-independent direction set

Let $T(n)$ denote the maximum number of unit distances that a set of $n$ points in the Euclidean plane $\mathbb{R}^2$ can determine with the additional condition that the distinct unit length directions determined by the configuration must be $\mathbb{Q}$-independent. This is related to the Erd\"os unit distance problem but with a simplifying additional assumption on the direction set that 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 $\Theta(n log(n))$. Furthermore, we describe a process to construct a set of $n$ points in the plane with $\mathbb{Q}$-independent unit length direction set that 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 $\mathbb{Z}^{\infty}$ or the infinite hypercube graph $\{0,1\}^{\infty}$. The problem of determining $T(n)$ can be viewed as either a type of packing or isoperimetric problem.

Anahtar Kelimeler:

Unit distance problem, discrete combinatorics, isoperimetric problems

A note on the unit distance problem for planar configurations with $\mathbb{Q}$-independent direction set

Keywords:

Unit distance problem, discrete combinatorics, isoperimetric problems,

PDF

___

Aronov B, Sharir M. Cutting circles into pseudo-segments and improved bounds for incidences. Discrete Comput Geom 2002; 28: 475–490.
Bernstein AJ. Maximally connected arrays on the n-Cube. SIAM J Appl Math 1967; 15: 1485–1489.
Bezrukov S. Isoperimetric problems in discrete spaces. In: Frankl P, F¨uredi Z, Katona G, Miklos D, editors. Extremal Problems for Finite Sets. Budapest, Hungary: Bolyai Math Stud, 1994; 3: pp. 59–91.
Brass P, Moser W, Pach J. Research Problems in Discrete Geometry. New York, NY, USA: Springer-Verlag, 2005.
Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Comput Geom 1990; 5: 99–160.
Erd¨os P. On a set of distances of n points. Am Math Mon 1946; 53: 248–250.
Guth L, Katz N. On the Erd¨os distinct distance problem on the plane. arXiv: 1011.4105 [math.CO].
Harper LH. Optimal assignment of numbers to vertices. J Soc Ind Appl Math 1964; 12: 131–135.
Hart S. A note on the edges of the n-Cube. Discrete Math 1976; 14: 157–163.
Matou˘sek J. The number of unit distances is almost linear for most norms. Adv Math 2011; 226: 2618–2628.
Munkres J. Elements of Algebraic Topology. Menlo Park, CA, USA: Addison-Wesley Publishing Company, 1984.
Spencer J, Szemer´edi E, Trotter WT. Unit distances in the Euclidean plane. In: Bollobas B, editor. Graph Theory and Combinatorics. New York, NY, USA: Academic Press, 1984, pp. 293–303.
Sz´ekely L. Crossing numbers and hard Erd¨os problems in discrete geometry. Comb Probab Comput 2005; 6: 353– 358.