4
$\begingroup$

Given a set of $n$ point in a plane, find the maximal number of colinear points (the points residing on the same straight line).

The crudest algorithm is to compute the slope and intercept of each pair of point, assuming infinite precision, find maximal number of appearance of the same pair of parameters.

Is there an algorithm more efficient (1) in the worst case, (2) on average? What is the optimal one (1) in the worst case which I suspect the crude method with complexity $n\choose 2$ is the optimal, (2) on average; and how to prove it?

$\endgroup$
3
$\begingroup$

Algorithm: RANSAC would be a good algorithm for this problem, if you think there exists a line such that a large fraction of points lie on that line. (However, if there is no such line, RANSAC is not a good choice.) In each iteration, it randomly selects two points, draws a line through them, and then checks how many other points fall onto that line. It then does many iterations repeatedly, and keeps the best line it has found so far.

Analysis: Suppose there exists a line $L$ such that a fraction $p$ of the points are on the line $L$. Then any particular iteration has a $p^2$ probability of picking two points on the line $L$ and discovering the line $L$. So, if you run RANSAC for $O(1/p^2)$ iterations, then with high probability the line $L$ will be detected. Each iteration takes $O(n)$ time, so the total running time will be $O(n/p^2)$. For some values of $p$, this will be faster than your crude algorithm (which has a $O(n^2)$ running time).

In short, the more points on the optimal line, the faster RANSAC will find it.


This doesn't answer your question about the best worst-case complexity. I don't know if it is possible to beat ${n \choose 2}$ worst-case complexity. I don't know if this is optimal or if there are better algorithms. Also, even in the case where we know there is a line containing many points and where we care about average-case complexity, I don't know if RANSAC is optimal or if one can do better.

$\endgroup$
2
  • $\begingroup$ Your complexity analysis is in the average sense and conditioned on the distribution of the points. Is it optimal on average, for, say, a set of points uniformly distributed in a square? The worst case complexity of this RANSAC method is still $O(n^2)$, right? $\endgroup$ – Hans Aug 3 '14 at 11:31
  • $\begingroup$ @Hans, yes, that is correct. Yes, its worst case complexity for a worst-case arrangement of points is at least $O(n^2)$ (could be even worse). RANSAC is probably only suitable if you think there is a line such that a large fraction of points lie on that line. If you don't think that's the case, then RANSAC is not a good choice. $\endgroup$ – D.W. Aug 4 '14 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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