In $\tilde{O}(n)$ time, can I generate $n$ random lattice points so that no four lie on the same circle? You can assume we pick points from a grid of side length $k \gg n$ (say, take $k=n^2$).

I have seen a similar problem about no 3 collinear, but I don't know if it's possible to adapt it for a circle.

If this is not possible, what is the closest we can get to random (i.e. anything that is pseudorandom and "random enough" that avoids four points on the same circle)? I'm not sure how to state this formally, but maybe a distribution that is as close to uniform as possible.

  • $\begingroup$ It should be noted that, in the answer you've linked they don't generate random points uniformly. They generate random points on "any random quadratic polynomial." Which will not be a uniform distribution across the Y coordinate. (Though it can be uniformly random on the X coordinate). Using a similar principle, you can most likely find some equation that will give you a similar result. (Where no matter where you pick your points, you won't be able to create a circle) $\endgroup$ Commented May 15 at 6:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.