4
$\begingroup$

Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) that given three points returns true if they are non collinear and false otherwise. Is there an efficient algorithm to generate a list of random points such that no 3 points in the list are collinear? The points coordinates x y are integers, the amount of points is N and the grid size is RxC, I know that there is a restriction between N and R C, so I am fine if the algorithm relies in some assumption (e.g RxC is way bigger than N)

$\endgroup$
  • $\begingroup$ Do you need some restrictions on the distribution generated? Some fixed shapes (e.g., points along the edge of an approximate circle; in general, the vertices of any convex shape) can be easily generated to have no three points collinear $\endgroup$ – Curtis F Jul 20 '18 at 23:11
  • $\begingroup$ Ideally I would want the points closer to uniformly distributed $\endgroup$ – dpalma Jul 20 '18 at 23:33
  • $\begingroup$ However any easy algorithm will do if it is random in some sense. $\endgroup$ – dpalma Jul 20 '18 at 23:43
5
$\begingroup$

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 < x_2 < 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 \}$.

$\endgroup$
  • $\begingroup$ Some points in the answer there are not clear, as why only two points can be considered in a row. Also, why a particular function of $(i, i^2 \ mod \ n)$ is considered, when collinearity is to be avoided. States to take any random quadratic function, but does not give the reason why? $\endgroup$ – jiten Dec 6 '20 at 9:20
  • 1
    $\begingroup$ If you have $3$ points in a row, they will be automatically collinear and hence we have max of $2$ points in a row. In the line where it talks about equating slopes of two lines by choosing two points each from any group of three points, it shows why it works. Unless the points are the same, the slopes would not match. $\endgroup$ – Math Lover Dec 8 '20 at 10:49
  • $\begingroup$ @MathLover Why only a particular quadratic value of $y_i = x_i^2\ mod\ n$ need be there, to check for collinearity, i.e. to get $x_3=x_1$. This particular value, seems to simply be based upon the algebraic fraction: $\frac{x_i^2 - x_{(i-1)}^2}{x_i - x_{(i-1)}}= x_i + x_{(i-1)}$ So, can we not chose other set of points than $(i, i^2\ mod\ n)$? $\endgroup$ – jiten Dec 18 '20 at 10:21
  • 1
    $\begingroup$ You can pick random quadratic polynomial $p$ with leading coefficient that is coprime to $n$. $\endgroup$ – Siong Thye Goh Dec 28 '20 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.