A note on the unit distance problem for planar configurations with Q-independent direction set
A note on the unit distance problem for planar configurations with Q-independent direction set
Let T(n) denote the maximum number of unit distances that a set of n points in the Euclidean plane R 2 can determine with the additional condition that the distinct unit length directions determined by the configuration must be 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 Θ(nlog(n)). Furthermore, we describe a process to construct a set of n points in the plane with 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 Z ∞ 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.
___
- Aronov B, Sharir M. Cutting circles into pseudo-segments and improved bounds for incidences. Discrete Comput Geom 2002; 28: 475490.
- Bernstein AJ. Maximally connected arrays on the n-Cube. SIAM J Appl Math 1967; 15: 14851489.
- 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. 5991.
- 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: 99160.
- Erd¨os P. On a set of distances of n points. Am Math Mon 1946; 53: 248250.
- 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: 131135.
- Hart S. A note on the edges of the n-Cube. Discrete Math 1976; 14: 157163.
- Matou˘sek J. The number of unit distances is almost linear for most norms. Adv Math 2011; 226: 26182628.
- 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. 293303.
- Sz´ekely L. Crossing numbers and hard Erd¨os problems in discrete geometry. Comb Probab Comput 2005; 6: 353 358.