ajay@cs.Buffalo.EDU (Ajay Shekhawat) (03/09/91)
I'd like references to the following problem: I want to pick N integer points (points with integer coordinates) so that no three of them are collinear. What is the size of the smallest square grid that is necessary? Clearly the grid must be atleast N/2 x N/2 . Any help would be appreciated. If there's sufficient interest, I'll post a summary of responses. Ajay.. Ajay Shekhawat <Dept. of Comp. Sci., SUNY@Buffalo, Amherst, NY 14260> ajay@cs.Buffalo.EDU || ajay@sunybcs.BITNET || ajay@sunybcs.UUCP || 716.636.3180
reingold@emr.cs.uiuc.edu (Edward M. Reingold) (03/09/91)
This is an old problem, going back at least to the early part of this century. Given an $n \times n$ array of $n^2$ points of the unit lattice, what is the largest number $T(n)$ of the points that can be chosen so that no three are on a line (``line'' here means vertical or horizontal, not diagonal)? Clearly $T(n) \leq 2n$ and $T(n)$ is known to equal $2n$ for $n \leq 24$. It is also known that $T(n) > (3/2 - \epsilon)n$ for all $\epsilon >0$. The problem can be generalized to an $n \times m$ grid. A related problem is to determine the smallest number of points in the $n \times n$ grid, no three in a line, such that the set of lines they determine covers all $n^2$ points of the grid. This problem was in Martin Gardner's Mathematical Games column of Scientific American in May, 1972, October, 1976, and March, 1977. There are many papers in the literature; see, for example, Journal of Combinatorial Theory, series A, vol. 18, pp. 336--341, vol. 20, pp. 363--364, vol. 24, pp. 126--127, vol. 26, pp. 82--83, and vol. 27, pp. 365--366. Also, see Richard K. Guy's Unsolved Problems in Number Theory, Springer-Verlag, 1981. -- Professor Edward M. Reingold reingold@cs.uiuc.edu Department of Computer Science (217) 333-6733 University of Illinois at Urbana-Champaign 1304 W. Springfield Ave. Urbana, IL 61801-2987 USA