A point set $P$ is said to be embedded in $\mathbf{Z}^2$ in *general position*, if no three points lie on a common line. Assume that $|P|=n$, I am interested in the smallest $k \times k$ integer grid in which $P$ can be embedded in general position? What can be said about $k$ as a function in $n$?


One idea is to place the points on the parabola, i.e., the $i$th point is placed at $(i,i^2)$. More general, every realization of a convex $n$-gon yields such an embedding - and convex $n$-gons can be embedded on a $\Theta(n^{3/2})\times\Theta(n^{3/2})$ grid.


My question is, can we realize a set of points in general position on a smaller integer grid?



Points in general position on a small grid
This is the "no three in a line" problem, and you will find many discussions of it if you type the quoted phrase into the internet and stand back. A starting place is the [Wikipedia](http://en.wikipedia.org/wiki/No-three-in-line_problem) page on the problem. 


