# Optimal Algorithm for Finding Maximal Number of Colinear Points

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?

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).
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.
• 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? – Hans Aug 3 '14 at 11:31
• @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. – D.W. Aug 4 '14 at 8:10