Points in general position on a small grid

Question

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?

Answer 1

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 page on the problem.