Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 798.52017
Autor: Erdös, Paul; Makai, Endre; Pach, János
Title: Nearly equal distances in the plane. (In English)
Source: Comb. Probab. Comput. 2, No.4, 401-408 (1993).
Review: The authors prove that for every positive integer k and for every \epsilon > 0 there exist numbers n0 > 0 and c > 0 such that every set of n > n0 points in the Euclidean plane in pairwise distances at least 1 has the following property: for arbitrary reals t1,..., tk, the number of pairs of points whose distance belongs to the set \bigcupi = 1k [ti, ti+c\sqrt{n}] is at most (n2/2) (1- 1/(k+1)+\epsilon). This bound is asymptotically best possible. The proof generalizes the considerations of the authors and J. Spencer [DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 4, 265-273 (1992; Zbl 741.52010)].
Reviewer: M.Lassak (Bydgoszcz)
Classif.: * 52C10 Erdoes problems and related topics of discrete geometry
Keywords: distance; graph; subgraph; points; Euclidean plane
Citations: Zbl 741.52010
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag