<p>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).</p>

<p>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 <a href="http://sarielhp.org/p/04/depth/depth.pdf" rel="nofollow noreferrer">http://sarielhp.org/p/04/depth/depth.pdf</a>). </p>

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

CC BY-SA 3.0
2016-11-07T18:51:59.760Z
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?
aelguindy
CC BY-SA 3.0
2016-11-07T18:56:32.047Z
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.
aelguindy
CC BY-SA 3.0
2016-11-11T12:28:40.820Z
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.
Sariel Har-Peled
CC BY-SA 3.0
2016-11-11T17:51:09.857Z
If I understand correctly, the conjecture used to be breaking the quadratic barrier by any amount and only after that result, was the conjecture weakened to the form you mention. But in any case, I am still glad to get an algorithm for colinear points that is subquadratic by any amount (even logarithmic).
aelguindy
CC BY-SA 3.0
2016-11-12T15:55:14.190Z
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](http://link.springer.com/article/10.1007/s00453-007-9036-3) several years earlier.
Jeffε
CC BY-SA 3.0
2016-11-12T15:59:24.990Z
(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}).
Jeffε
CC BY-SA 3.0
2016-11-12T16:50:24.633Z
I think you meant $O(n^{1.9999999999999999})$.
Sariel Har-Peled
CC BY-SA 3.0
2016-11-07T18:32:36.273Z
2016-11-07T18:32:36.273Z
Sariel Har-Peled
<p><strong>The problem</strong>: given a set of points in the Euclidean plane, find the maximum number of co-linear points.</p>

<p>I already know that the problem can be solved in quadratic time using hashing or projective duality (as described <a href="http://www.ti.inf.ethz.ch/ew/Lehre/CG13/lecture/Chapter%2011.pdf" rel="nofollow noreferrer">here</a>). I also know that checking whether three points are co-linear was proven to be 3SUM-hard under sub-quadratic reductions <a href="http://www.sciencedirect.com/science/article/pii/0925772195000222" rel="nofollow noreferrer">here</a>.</p>

<p>There are a few issues however:</p>

<ol>
<li>The 3SUM conjecture was proven false <a href="https://arxiv.org/abs/1404.0799" rel="nofollow noreferrer">here</a>, so it is no longer believed that the problem has a quadratic lower bound (unless it is strictly harder than 3SUM, see next point).</li>
<li>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.</li>
<li>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.</li>
</ol>

<p><strong>My question is:</strong> 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?</p>

<p>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.</p>

<p>EDIT: I am also (but not exclusively) interested in the case when the coordinates are integral.</p>

CC BY-SA 3.0
2016-11-12T15:23:44.193Z
http://www.sciencedirect.com/science/article/pii/0925772195000208
Jeffε
CC BY-SA 3.0
2016-11-13T00:25:42.590Z
@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.
aelguindy
<ds.algorithms><computational-geometry><complexity>
Complexity of counting maximum number of co-linear points in Euclidean plane
aelguindy
# Complexity of counting maximum number of co-linear points in Euclidean plane

(Asked by: username_0 on 2016-11-06)

**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](http://www.ti.inf.ethz.ch/ew/Lehre/CG13/lecture/Chapter%2011.pdf)). I also know that checking whether three points are co-linear was proven to be 3SUM-hard under sub-quadratic reductions [here](http://www.sciencedirect.com/science/article/pii/0925772195000222).

There are a few issues however:

1. The 3SUM conjecture was proven false [here](https://arxiv.org/abs/1404.0799), 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.

**Tags:** ds.algorithms, computational-geometry, complexity

> **Comments:**
> **username_1**: http://www.sciencedirect.com/science/article/pii/0925772195000208  
> **username_0**: @username_1 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.  

---

## 1 answers

### Answer by username_2 on 2016-11-07. Score: 3

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

> **Comments:**
> **username_0**: 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?  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: If I understand correctly, the conjecture used to be breaking the quadratic barrier by any amount and only after that result, was the conjecture weakened to the form you mention. But in any case, I am still glad to get an algorithm for colinear points that is subquadratic by any amount (even logarithmic).  
> **username_1**: 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](http://link.springer.com/article/10.1007/s00453-007-9036-3) several years earlier.  
> **username_1**: (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}).  
> **username_2**: I think you meant $O(n^{1.9999999999999999})$.  

---

