# Complexity of counting maximum number of co-linear points in Euclidean plane

The problem: given a set of points in the Euclidean plane, find the maximum number of co-linear points.

I already know that the problem can be solved in quadratic time using hashing or projective duality (as described here). I also know that checking whether three points are co-linear was proven to be 3SUM-hard under sub-quadratic reductions here.

There are a few issues however:

1. The 3SUM conjecture was proven false here, so it is no longer believed that the problem has a quadratic lower bound (unless it is strictly harder than 3SUM, see next point).
2. Unlike most problems in the 3SUM-conjecture paper, co-linearity was only proven to be at least as hard as 3SUM, a reduction in the other direction was not given. That is, it still may be the case that co-linearity is strictly harder than 3SUM. Therefore, the sub-quadratic algorithm for 3SUM cannot be immediately used for the co-linearity problem.
3. 3SUM references only address the problem of checking whether at least 3 points are co-linear. It is not clear to me how to reduce the problem of counting the maximum number of co-linear points to that without a multiplicative linear factor.

My question is: is there any sub-quadratic algorithm known for the problem? If not, do we have a good reason to believe that such an algorithm does not exist?

It is known that finding an $O(n^{2-\epsilon})$ algorithm for 3SUM is still open. So I am, at best, hoping for a logarithmic improvement over the quadratic algorithm.

EDIT: I am also (but not exclusively) interested in the case when the coordinates are integral.

• sciencedirect.com/science/article/pii/0925772195000208 Nov 12, 2016 at 15:23
• @Jeffε thanks for the link. If I understand correctly, in the case where only a constant number of points are co-linear, the paper's algorithm is quadratic. (I guess that's why you posted this as a comment, rather than an answer). It is still useful to add the name "exact-fitting" to my future search of other results. Nov 13, 2016 at 0:25

As for your question, if you are looking for a line containing more than $k$ points, and $k$ is sufficiently large (at least say $10\log^2 n$), then it is not hard to get a subquadratic number of candidate lines such that one of them with high probability is the desired line. Then using standard trade-offs between space and query time for range searching, you would get something subquadratic. The question is of course what to do in the in-between range, when the heaviest line has between $3$ and polylog n points on it. (For ref, see http://sarielhp.org/p/04/depth/depth.pdf).
I think the interesting open question, is whether one can get $O(n^2/k^2)$ (the above would get you at best $O(n^2/k^2 * polylog n)$ [but its probably slower than that]).
• The algorithm in Section 5.1 gets running time $O(n^2/log n)$ (or something similar). This is not considered as breaking the 3sum conjecture. For that, you would want an algorithm with running time $O(n^{2-\eps})$, where $\eps > 0$ is some fixed constant. Nov 11, 2016 at 12:28