Given n points on the plane, it is a standard interview problem to find the line with the maximum points, which can be done in O(n^2) with pivoting + hashmaps or other method.
Question: Are there more efficient algorithms that runs in o(n^2) e.g. O(nlogn), solving:
(1) Find the line containing maximum number of points, and/or
(2) Find the maximum number of points possible on a single line
Originally I thought O(n^2) would be optimal, but it turns out that the 3-colinear problem has been shown to be o(n^2) by Grønlund, Pettie in 2014. What about the general case then? Is there any o(n^2) reduction between the two problems?
Note that this is a duplicate of a 2014 problem, but since then there has been a lot of development in 3SUM problems.