A003034 Sylvester's problem: minimal number of ordinary lines through n points in the plane. (Formerly M2275)

3, 3, 4, 3, 3, 4, 6, 5, 6, 6, 6, 7

Offset

3,1

Comments

An ordinary line contains exactly 2 points. The problem is to place n points, not all on a line, so as to minimize the number of ordinary lines.

Pach and Sharir give the following table for n >= 3: 3, 3, 4, 3, 3, 4, 6, 5, 6, 6, 6, 7, ?, 8, ?, 9, ?, ?, ?, 11, ... - N. J. A. Sloane, Dec 01 2010

References

J. Brakke, Some new values for Sylvester's function for n collinear points, J. Undergrad. Math., 4 (1972), 11-14.

H. T. Croft, K. J. Falconer and R. K. Guy, Unsolved Problems in Geometry, F12.

B. Grünbaum, Arrangements and Spreads. American Mathematical Society, Providence, RI, 1972, p. 18.

S. Hansen, Contributions to the Sylvester-Gallai theory, Dissertation, Univ. Copenhagen, 1981. [Csima and Sawyer point out errors in this dissertation.]

J. Pach and M. Sharir, Combinatorial Geometry and Its Algorithmic Applications, Amer. Math. Soc., 2009; see p. 2.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=3..14.

P. Borwein and W. O. J. Moser, A survey of Sylvester's problem and its generalizations, Aequat. Math., 40 (1990), 111-135.

D. W. Crowe and T. A. McKee, Sylvester's problem on collinear points, Math. Mag., 41 (1968), 30-34.

J. Csima and E. T. Sawyer, There exist 6n/13 ordinary points, Discrete & Computational Geometry, 9 (1993), 187-202.

L. M. Kelley and W. O. J. Moser, On the number of ordinary lines determined by n points, Canad. J. Math., 10 (1958), 210-219.

Formula

Kelly and Moser showed that a(n) >= ceiling(3n/7); Csima and Sawyer showed that a(n) >= floor(6n/13) except for n=7.

Crossrefs

Sequence in context: A188590 A080038 A121937 * A091282 A202708 A027684

Adjacent sequences: A003031 A003032 A003033 * A003035 A003036 A003037

Keyword

nonn,hard,nice

Author

N. J. A. Sloane

Status

approved