On the distinct distances determined by a planar point set

ABSTRACT

It is shown that every set of $n$ points in the plane has an element f rom which there are at least $cn^{6/7}$ other elements at distinct distances, where $c>0$ is a constant. This improves earlier results of Erd\H os, Moser, Beck, Chung, Szemer\'edi, Trotter, and Sz\'ekely.

REFERENCES

• 1: M. Ajtai, V. Chvatal, M. Newborn, and E. Szemeredi, Crossing-free graphs, Ann. Discrete Math. 12 (1982), 9-12.
• 2: J. Beck, On the lattice property of the plane and some problems of Dirac, Motzkin and Erdos in combinatorial geometry, Combinatorica 3 (1983), 281-297.
• 3: F. R. K. Chung, The number of different distances determined by n points in the plane, J. Combin. Theory Ser. A 36 (1984), 342-354.
• 4: Fan R. K. Chung , E. Szemerédi , W. T. Trotter, The number of different distances determined by a set of points in the Euclidean plane, Discrete & Computational Geometry, v.7 n.1, p.1-11, 1992 [doi>10.1007/BF02187820]
• 5: Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
• 6: P. Erdos, On sets of distances of n points, Amer. Math. Monthly 53 (1946), 248-250.
• 7: F. T. Leighton, Complexity issues in VLSI, MIT Press, 1983.
• 8: L. Moser, On the different distances determined by n points, Amer. Math. Monthly 59 (1952), 85-91.
• 9: J. Pach and P. K. Agarwal: Combinatorial Geometry, Wiley, NewYork, 1995.
• 10: János Pach , Micha Sharir, On the Number of Incidences Between Points and Curves, Combinatorics, Probability and Computing, v.7 n.1, p.121-127, March 1998 [doi>10.1017/S0963548397003192]
• 11: László A. Székely, Crossing Numbers and Hard Erdös Problems in Discrete Geometry, Combinatorics, Probability and Computing, v.6 n.3, p.353-358, September 1997 [doi>10.1017/S0963548397002976]
• 12: E. Szemeredi and W. T. Trotter, Extremal problems in discrete geometry, Combinatorica 3 (1983), 381-392.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Theory, Verification

Keywords:
Szemer\ 'edi-Trotter theorem, crossing number, planar point set