3
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Random with what distribution? $\endgroup$ Mar 1, 2014 at 23:17

3 Answers 3

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks! I haven't made experiments yet, but this looks like a very promising approach. $\endgroup$ Mar 3, 2014 at 14:20
2
$\begingroup$

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.
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – FrankW
    Mar 1, 2014 at 22:46
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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