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:


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).
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.
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.
First, my understanding is that the paper you linked to does not show that 3sum is incorrect. It just shows that the 3sum conjecture is false in a model of computation that is not realistic (i.e., we do not have currently a truly subquadratic algorithm for 3sum).

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