Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?
For simplicity , assume the grid is a square $N \times N$ grid and $N$ is a prime.

Its easy to see that from each row we can pick $\leq 2$ points only , so the maximum number of points we can chose is $2N$.

Now consider the set of points $\{(i,i^2\ mod\ n)\ |\ 0\leq i \leq n-1 \}$.

For any set of 3 points to be collinear (Lets call them $(x_1,y_1),(x_2,y_2),(x_3,y_3) , x_1 &lt; x_2 &lt; x_3$ ) we must have $\frac{y_3 - y_2}{x_3 - x_2} = \frac{y_2 - y_1}{x_2 - x_1}$ , putting in $y_i = x_i^2\ mod\ n$ , we obtain $x_3 + x_2 \equiv x_2 + x_1 \mod n$ and this is only possible when $x_1 = x_3$.

Hence we have a set of $N$ points where no 3 points are collinear and it is the best we can obtain upto a constant factor.

Since this is a deterministic construction , to get a random family of points , instead of choosing $i^2$ , we can take any random quadratic polynomial $p$ and take the set of points $\{(i , p(i)) \ mod\ n \ |\ 0 \leq i \leq n-1 \}$.