How will you find a random collection of $n$ points in the plane, all with integer coordinates in a specified range (e.g. -1000 to 1000), such that no 3 of them are on the same line?
The following algorithm eventually works, but seems highly inefficient:
- Select $n$ points at random.
- Check all $O(n^3)$ triples of points. If any of them are on the same line, then discard one of the points, select an alternative point at random, and go back to 2.
Is there a more efficient algorithm?
Asked By : Erel Segal-Halevi
Answered By : D.W.
Here's an approach that I think achieves $O(n^2)$ running time, as long as the points are not too dense (as long as $n$ is not too large compared to the size of the region).
Store the set of all slopes of lines between any pair of points. There are $O(n^2)$ pairs of points, and each pair of points determines line; add that line to the set. I suggest you store this as a hash table that maps the slope $s$ to the set of pairs $(P,Q)$ of points which are at slope $s$ from each other.
Now to add a new point, pick a point $R$ uniformly at random. Pair $R$ up with each other point, say $P$. Compute the slope of the line from $P$ to $R$. Look up that slope in the hash table, and see whether the corresponding set contains the point $P$. The latter can be done in $O(1)$ expected time if you use suitable data structures for the hash table and for storing the set (in particular, the entry corresponding to slope $s$ can be a hash-set of all of the points that participate in a pair whose slope is $s$). Since $R$ can be paired up with $n$ other points, this check will take $O(n)$ expected time.
Now as long as the number of points is not too dense (so that you don't reject a point more than a constant fraction of the time), the expected running time will be $O(n^2)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/22167
0 comments:
Post a Comment
Let us know your responses and feedback