Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!usc!wuarchive!zaphod.mps.ohio-state.edu!ub!ajay
From: ajay@cs.Buffalo.EDU (Ajay Shekhawat)
Newsgroups: comp.theory
Subject: Non-collinear points on a grid.
Message-ID: <64124@eerie.acsu.Buffalo.EDU>
Date: 8 Mar 91 23:05:08 GMT
Sender: news@acsu.Buffalo.EDU
Reply-To: ajay@cs.Buffalo.EDU ( Ajay Shekhawat )
Organization: University at Buffalo, Dept. of Computer Science
Lines: 12
Nntp-Posting-Host: sybil.cs.buffalo.edu
Originator: ajay@sybil.cs.Buffalo.EDU

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