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)
$\begingroup$
$\endgroup$
3
-
$\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 FJul 20, 2018 at 23:11
-
$\begingroup$ Ideally I would want the points closer to uniformly distributed $\endgroup$– dpalmaJul 20, 2018 at 23:33
-
$\begingroup$ However any easy algorithm will do if it is random in some sense. $\endgroup$– dpalmaJul 20, 2018 at 23:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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 \}$.
-
$\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$– jitenDec 6, 2020 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$ Dec 8, 2020 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$– jitenDec 18, 2020 at 10:21
-
1$\begingroup$ You can pick random quadratic polynomial $p$ with leading coefficient that is coprime to $n$. $\endgroup$ Dec 28, 2020 at 4:11
-
$\begingroup$ I think this approach doesn't cover cases with 3 points being on one diagonal $\endgroup$ May 25, 2022 at 2:41