4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ sciencedirect.com/science/article/pii/0925772195000208 $\endgroup$
    – Jeffε
    Nov 12, 2016 at 15:23
  • $\begingroup$ @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. $\endgroup$
    – aelguindy
    Nov 13, 2016 at 0:25

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ Re your first paragraph, unless I have a major misunderstanding, the algorithm given in section 5.1 is subquadratic and is not making any non-standard computational model assumptions.. What am I missing? $\endgroup$
    – aelguindy
    Nov 7, 2016 at 18:51
  • $\begingroup$ And although I do not fully understand the details of the explanation in your second paragraph, it is definitely not hard to see that if the number of co-linear points sought is large enough, then randomization will do very well. For me, the constant-number-of-points version is the most interesting sub-problem. So the problem you pose in your last paragraph, despite being interesting, is not what I am looking for an answer for. $\endgroup$
    – aelguindy
    Nov 7, 2016 at 18:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sariel Har-Peled
    Nov 11, 2016 at 12:28
  • 2
    $\begingroup$ I disagree with the first sentence. Grønlund and Pettie's results do prove that 3SUM can be solved in (slightly) subquadratic time in a realistic model of computation. The algorithm is described in the real RAM, but since it avoids multiplication, it translated to the word RAM with the same running time. On the other hand, (slightly) subquadratic algorithms in the word RAM were already shown by Baran, Demaine, and Patrascu several years earlier. $\endgroup$
    – Jeffε
    Nov 12, 2016 at 15:55
  • 1
    $\begingroup$ (cont'd) The Baran-Demaine-Patrascu results already changed "the 3SUM conjecture" from "every algorithm for 3SUM requires Ω(n^2) time" to "every algorithm for 3SUM requires Ω(n^{2-ε}) time for all ε>0". In light of these results, the existence a (slightly) subquadratic algorithm to detect collinearities—both in the word RAM and the real RAM—is a near certainty. But it won't really be interesting unless the running time is O(n^{1.99999999999999}). $\endgroup$
    – Jeffε
    Nov 12, 2016 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.