Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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:

  1. Select $n$ points at random.
  2. 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?

share|improve this question
1  
Random with what distribution? –  David Richerby Mar 1 at 23:17

3 Answers 3

up vote 3 down vote accepted

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)$.

share|improve this answer
    
Thanks! I haven't made experiments yet, but this looks like a very promising approach. –  Erel Segal Halevi Mar 3 at 14:20

You can improve on your algorithm while keeping the general idea:

  1. Draw 2 points at random and add them to the (previously empty) set of selected points.
  2. Draw a new point at random. Check all triples involving two of the previously selected points and the new point. If one of them fails, dicard the new point. Otherwise add it to the set of selected points.
  3. If you have $n$ nodes selected, terminate. Otherwise goto 2.
share|improve this answer
1  
Expected runtime depends on the probability of collisions. If no or only few collisions occur it's $\Theta(n^3)$. Note that testing a new point is $\cal O(m^2)$, where $m$ is the number of previously selected points. –  FrankW Mar 1 at 22:46

There's a simple approach with running time proportional to $2000 n^2$ (for your example parameters).

Keep a hash table that stores all of the points that are forbidden. For each pair of points $P,Q$, you extend the line from $P$ to $Q$ and add to the hash table all points with integral coefficients that are on that line. Each time you pick a new point, you check it against the hash table (if it is forbidden, go back and pick a new one), then you pair it up with all other points and add to the hash table.

This might work well in practice if the specified range is small, but if the range is large, it will scale poorly.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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