# Optimal time complexity to solve "maximum points on line"

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.

Thank you.

• You may already be aware of this post, but check it out if that's not the case. Jan 19, 2023 at 21:03
• @Nathaniel The only answer seems to be by Shlomo Pongratz, where he suggested to map to the dual space, "find all intersections in O(nlogn)", then count the maximum intersections (i.e. find point where maximum number of lines pass through it). However, the number of intersections can be O(n^2), so this won't work. Jan 19, 2023 at 21:14
• I was mainly refering to the first answer by jonderry for a reduction from the 3SUM problem to the maximum colinear problem, since you asked about it. Jan 19, 2023 at 21:28
• @Nathaniel i think the reduction is in the opposite direction, unless i misunderstood the answer. Jan 20, 2023 at 5:23
• The answer shows how to solve the 3SUM problem assuming one can solve the max colinear problem. This is exactly a reduction from 3SUM to the max colinear problem. Jan 20, 2023 at 6:43