Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?
-
05-11-2019 - |
Question
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)
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange