A tight bound for the number of different directions in three dimensions

ABSTRACT

Let P be a set of n points in R³, not all of which are in a plane and no three on a line. We partially answer a question of Scott (1970) by showing that the connecting lines of P assume at least 2n-3 different directions if n is even and at least 2n-2 if n is odd. These bounds are sharp. The proof is based on a far-reaching generalization of Ungar's theorem concerning the analogous problem in the plane.

REFERENCES

• 1: M. Aigner and G. Ziegler. Proofs from The Book (including illustrations by Karl H. Hofmann), 2nd ed. Springer-Verlag, Berlin, 2001.
• 2: J. Beck. On the lattice property of the plane and some problems of dirac, motzkin and erdos in combinatorial geometry. Combinatorica, 3:281--297, 1983.
• 3: P. Borwein and W. O. J. Moser. A survey of sylvester's problem and its generalizations. Aequationes Math., 40:111--135, 1990.
• 4: J. Braams. The number of directions determined by points in the three-dimensional euclidean space. Discrete Comput. Geom., 28:491--494, 2002.
• 5: G. D. Chakerian. Sylvester's problem on collinear points and a relative. Amer. Math. Monthly, 77:164--167, 1970.
• 6: R. Cordovil. The directions determined by n points in the plane, a matroidal generalization. Discrete Math., 43:131--137, 1983.
• 7: J. E. Goodman and R. Pollack. A combinatorial perspective on some problems in geometry. Congr. Numer., 32:383--394, 1981.
• 8: J. E. Goodman and R. Pollack. Allowable sequences and order types in discrete and computational geometry. Algorithms Combin., 10:103--134, 1993.
• 9: B. Grünbaum. Arrangements of colored lines. Notices Amer. Math. Soc., 22:A--200, 1975.
• 10: B. Grünbaum. Monochromatic intersection points in families of colored lines. Geombinatorics, IX:3--9, 1999.
• 11: R. E. Jamison. Survey of the slope problem. Discrete Geometry and Convexity, 440:34--51, 1985.
• 12: R. E. Jamison and D. Hill. A catalogue of sporadic slope-critical configurations. volume 40, pages 101--125, 1983.
• 13: T. S. Motzkin. Nonmixed connecting lines. Notices Amer. Math. Soc., 14:837, 1967.
• 14: P. E. os. Solution to problem nr. 4065. Amer. Math. Monthly, 51:169, 1944.
• 15: P. E. os and G. Purdy. Some combinatorial problems in the plane. J. Combinatorial Theory, Ser. A, 25:205--210, 1978.
• 16: P. R. Scott. On the sets of directions determined by n points. Amer. Math. Monthly, 77:502--505, 1970.
• 17: E. Szemerédi and J. W.T. Trotter. Extremal problems in discrete geometry. Combinatorica, 3:381--392, 1983.
• 18: P. Ungar. 2n noncollinear points determine at least 2n directions. J. Combin. Theory, Ser. A, 33:343--347, 1982.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Theory

Keywords:
Ungar's theorem, directions, slope problem