0
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ You may already be aware of this post, but check it out if that's not the case. $\endgroup$
    – Nathaniel
    Jan 19 at 21:03
  • $\begingroup$ @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. $\endgroup$
    – Gareth Ma
    Jan 19 at 21:14
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Jan 19 at 21:28
  • $\begingroup$ @Nathaniel i think the reduction is in the opposite direction, unless i misunderstood the answer. $\endgroup$
    – Gareth Ma
    Jan 20 at 5:23
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Jan 20 at 6:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.