<p>This is not a complete answer, but is too long for a comment.</p>
<p>Consider the following generalization of your problem: (Maximum Weight Halfplane) We are given a set <span class="math-container">$S$</span> of <span class="math-container">$m$</span> weighted points in the plane, and a special point <span class="math-container">$p\in S$</span>. Find a line such that the sum of the weights lying on the same side as <span class="math-container">$p$</span> is maximized.</p>
<p>Recall also the (integer) 3SUM problem: Given an array <span class="math-container">$A$</span> of <span class="math-container">$m$</span> distinct integers, does there exist three distinct elements <span class="math-container">$a,b,c \in A$</span> such that <span class="math-container">$a+b+c=0$</span>?</p>
<p>Claim: If we can solve the Maximum Weight Halfplane problem in time <span class="math-container">$O(m^{2-\alpha})$</span> for some <span class="math-container">$0&lt;\alpha&lt;1$</span>, then we can solve 3SUM in time <span class="math-container">$O(m^{2-\alpha})$</span>.</p>
<p>Sketch of a reduction:</p>
<p>Start with an instance <span class="math-container">$A$</span> of 3SUM. Let <span class="math-container">$\epsilon = 1/5$</span>. For <span class="math-container">$0\leq i\leq m-1$</span>, define <span class="math-container">$p_i = (A[i], A[i]^3)$</span>, <span class="math-container">$p^+_i = (A[i], A[i]^3+\epsilon)$</span>, <span class="math-container">$p^-_i = (A[i], A[i]^3+\epsilon)$</span>. Let the weights be <span class="math-container">$w(p_i^+)= 1$</span> and <span class="math-container">$w(p_i^-)= -1$</span>.
Define an additional point <span class="math-container">$p=(0, \infty)$</span>, with weight <span class="math-container">$w(p) = 10m$</span>.</p>
<p>Consider the instance of Maximum Weight Halfplane <span class="math-container">$S=\{p\}\cup(\bigcup_{0\leq i\leq m-1}\{p_i^+,p_i^-\})$</span>, where the special point is <span class="math-container">$p$</span>.</p>
<p>Note that the maximum weight halfplane necessarily contains <span class="math-container">$p$</span>. Moreover, if the maximum weight is at least <span class="math-container">$10m+3$</span>, this means there are at least three distinct indices <span class="math-container">$i_1,i_2,i_3$</span>, such that the separating line passes between <span class="math-container">$p_{i_1}^-$</span> and <span class="math-container">$p_{i_1}^+$</span>, between <span class="math-container">$p_{i_2}^-$</span> and <span class="math-container">$p_{i_2}^+$</span>, and between <span class="math-container">$p_{i_3}^-$</span> and <span class="math-container">$p_{i_3}^+$</span>. Thus, the line passes through three points <span class="math-container">$(A[i_1], A[i_1]^3+\delta_{i_1})$</span>, <span class="math-container">$(A[i_2], A[i_2]^3+\delta_{i_2})$</span> and <span class="math-container">$(A[i_3], A[i_3]^3+\delta_{i_3})$</span>, where <span class="math-container">$=-\epsilon \leq \delta_{i_1},\delta_{i_2},\delta_{i_2} \leq \epsilon$</span>. Some algebraic manipulation shows that this is equivalent to
<span class="math-container">$$(A[i_2]-A[i_1])(A[i_1]+A[i_2]+A[i_3]) = \frac{\delta_{i_3}-\delta_{i_1}}{A[i_3]-A[i_1]} - \frac{\delta_{i_2}-\delta_{i_1}}{A[i_2]-A[i_1]}.$$</span>
Assuming <span class="math-container">$A[i_1]+A[i_2]+A[i_3] \neq 0$</span>, and because these are all distinct integers, the left hand side in absolute value would be at least <span class="math-container">$1$</span>, but the right hand side in absolute value is at most <span class="math-container">$4\epsilon &lt; 1$</span>, which is a contradiction. Thus <span class="math-container">$A[i_1]+A[i_2]+A[i_3] = 0$</span>.</p>
<p>The same kind of reasoning works the other way around: if there are three indices such that <span class="math-container">$A[i_1]+A[i_2]+A[i_3] = 0$</span>, then you can find a hyperplane of weight at least <span class="math-container">$10m+3$</span> containing <span class="math-container">$p$</span>.</p>
<hr />
<p>Thus, if the 3-SUM conjecture is true, then you can't solve Maximum Weight Halfplane in strongly subquadratic time. In your problem you have <span class="math-container">$m=n^2$</span>, so this would give an <span class="math-container">$\tilde{\Omega}(n^4)$</span> lower bound (if the reduction worked for points on an <span class="math-container">$n\times n$</span> grid, which unfortunately it doesn't).</p>

CC BY-SA 4.0
2023-12-22T17:23:53.013Z
What is your current feeling about the hardness of my grid based problem?
Simd
CC BY-SA 4.0
2023-12-23T22:49:28.330Z
@Simd I don't have a strong feeling either way, would need to think about it more.
Tassle
CC BY-SA 4.0
2023-12-30T09:05:04.237Z
It's a shame no one was able to improve this.
Simd
CC BY-SA 4.0
2023-12-22T12:40:20.203Z
2023-12-22T12:40:20.203Z
Tassle
<p>I recently asked the following algorithms question on <a href="https://codegolf.stackexchange.com/questions/268581/finding-the-optimal-straight-line-boundary">another site</a>. The best answer so far is <span class="math-container">$O(n^4)$</span> time. The input is of size <span class="math-container">$O(n^2)$</span> and the output is just a number so I was wondering if there is a reduction from another problem with a known conditional lower bound that suggest <span class="math-container">$\Theta(n^4)$</span> is the correct complexity. Here is a slightly edited version of the problem.</p>
<p>Consider an <span class="math-container">$n \times n$</span> grid of integers. The task is to draw a straight line across the grid so that the part that includes the top left corner sums to the largest number possible.  Here is a picture of an optimal solution with score 45:</p>
<p><a href="https://i.sstatic.net/Oq6xh.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Oq6xh.png" alt="enter image description here" /></a></p>
<p>We include a square in the part that is to be summed if its middle is above or on the line. Above means in the part including the top left corner of the grid. (To make this definition clear, no line can start exactly in the top left corner of the grid.)</p>
<p>The task is to choose the line that maximizes the sum of the part that includes the top left square. The line must go straight from one side to another. The line can start or end anywhere on a side and not just at integer points.</p>
<p>I am interested it worst case time complexity as a function of <span class="math-container">$n$</span>.</p>

CC BY-SA 4.0
2023-12-21T19:04:49.797Z
I believe that if the points were not restricted to be on a grid, then you could show the problem for $m$ points is 3-SUM hard, meaning that if the 3-SUM conjecture is true you can't do $O(m^{2-\epsilon})$ for any $\epsilon > 0$ (in your case $m=n^2$, so that it would match the upper bound). That's not an answer for the grid version though.
Tassle
CC BY-SA 4.0
2023-12-21T19:31:05.630Z
can you clarify the link with 3SUM
kodlu
CC BY-SA 4.0
2023-12-21T19:34:58.087Z
Have you made any partial progress you can share?  As stated, there are infinitely many possible lines.  Do you know of any results that it's sufficient to consider a finite set of lines?  Perhaps all lines that go through some pair of points?  Or all lines that go through some point on the left side of the grad and some point on the bottom side of the grid?  How small can you make that set?  Is it sufficient to consider $O(n^2)$ many lines?
D.W.
CC BY-SA 4.0
2023-12-21T19:40:05.143Z
@D.W. The linked algorithm runs in $O(n^4)$ time and looks correct. It is missing a proof however.
Simd
CC BY-SA 4.0
2023-12-22T00:05:19.567Z
@Simd, Yup, I know, I did look at it.  I think my question remains relevant.
D.W.
<ds.algorithms><lower-bounds>
Is there a lower bound for the problem of finding the best straight line partition
Simd
# Is there a lower bound for the problem of finding the best straight line partition

(Asked by: username_0 on 2023-12-21)

I recently asked the following algorithms question on [another site](https://codegolf.stackexchange.com/questions/268581/finding-the-optimal-straight-line-boundary). The best answer so far is $O(n^4)$ time. The input is of size $O(n^2)$ and the output is just a number so I was wondering if there is a reduction from another problem with a known conditional lower bound that suggest $\Theta(n^4)$ is the correct complexity. Here is a slightly edited version of the problem.

Consider an $n \times n$ grid of integers. The task is to draw a straight line across the grid so that the part that includes the top left corner sums to the largest number possible. Here is a picture of an optimal solution with score 45:

[![enter image description here](https://i.sstatic.net/Oq6xh.png)](https://i.sstatic.net/Oq6xh.png)

We include a square in the part that is to be summed if its middle is above or on the line. Above means in the part including the top left corner of the grid. (To make this definition clear, no line can start exactly in the top left corner of the grid.)

The task is to choose the line that maximizes the sum of the part that includes the top left square. The line must go straight from one side to another. The line can start or end anywhere on a side and not just at integer points.

I am interested it worst case time complexity as a function of $n$.

**Tags:** ds.algorithms, lower-bounds
> **Comments:**
> **username_1**: I believe that if the points were not restricted to be on a grid, then you could show the problem for $m$ points is 3-SUM hard, meaning that if the 3-SUM conjecture is true you can't do $O(m^{2-\epsilon})$ for any $\epsilon > 0$ (in your case $m=n^2$, so that it would match the upper bound). That's not an answer for the grid version though.  
> **username_2**: can you clarify the link with 3SUM  
> **username_3**: Have you made any partial progress you can share?  As stated, there are infinitely many possible lines.  Do you know of any results that it's sufficient to consider a finite set of lines?  Perhaps all lines that go through some pair of points?  Or all lines that go through some point on the left side of the grad and some point on the bottom side of the grid?  How small can you make that set?  Is it sufficient to consider $O(n^2)$ many lines?  
> **username_0**: @D.W. The linked algorithm runs in $O(n^4)$ time and looks correct. It is missing a proof however.  
> **username_3**: @Simd, Yup, I know, I did look at it.  I think my question remains relevant.  

---

## 1 answers

### Answer by username_1 on 2023-12-22. Score: 2

This is not a complete answer, but is too long for a comment.

Consider the following generalization of your problem: (Maximum Weight Halfplane) We are given a set $S$ of $m$ weighted points in the plane, and a special point $p\in S$. Find a line such that the sum of the weights lying on the same side as $p$ is maximized.

Recall also the (integer) 3SUM problem: Given an array $A$ of $m$ distinct integers, does there exist three distinct elements $a,b,c \in A$ such that $a+b+c=0$?

Claim: If we can solve the Maximum Weight Halfplane problem in time $O(m^{2-\alpha})$ for some $0<\alpha<1$, then we can solve 3SUM in time $O(m^{2-\alpha})$.

Sketch of a reduction:

Start with an instance $A$ of 3SUM. Let $\epsilon = 1/5$. For $0\leq i\leq m-1$, define $p\_i = (A[i], A[i]^3)$, $p^+\_i = (A[i], A[i]^3+\epsilon)$, $p^-\_i = (A[i], A[i]^3+\epsilon)$. Let the weights be $w(p\_i^+)= 1$ and $w(p\_i^-)= -1$.
Define an additional point $p=(0, \infty)$, with weight $w(p) = 10m$.

Consider the instance of Maximum Weight Halfplane $S=\{p\}\cup(\bigcup\_{0\leq i\leq m-1}\{p\_i^+,p\_i^-\})$, where the special point is $p$.

Note that the maximum weight halfplane necessarily contains $p$. Moreover, if the maximum weight is at least $10m+3$, this means there are at least three distinct indices $i\_1,i\_2,i\_3$, such that the separating line passes between $p\_{i\_1}^-$ and $p\_{i\_1}^+$, between $p\_{i\_2}^-$ and $p\_{i\_2}^+$, and between $p\_{i\_3}^-$ and $p\_{i\_3}^+$. Thus, the line passes through three points $(A[i\_1], A[i\_1]^3+\delta\_{i\_1})$, $(A[i\_2], A[i\_2]^3+\delta\_{i\_2})$ and $(A[i\_3], A[i\_3]^3+\delta\_{i\_3})$, where $=-\epsilon \leq \delta\_{i\_1},\delta\_{i\_2},\delta\_{i\_2} \leq \epsilon$. Some algebraic manipulation shows that this is equivalent to
$$(A[i\_2]-A[i\_1])(A[i\_1]+A[i\_2]+A[i\_3]) = \frac{\delta\_{i\_3}-\delta\_{i\_1}}{A[i\_3]-A[i\_1]} - \frac{\delta\_{i\_2}-\delta\_{i\_1}}{A[i\_2]-A[i\_1]}.$$
Assuming $A[i\_1]+A[i\_2]+A[i\_3] \neq 0$, and because these are all distinct integers, the left hand side in absolute value would be at least $1$, but the right hand side in absolute value is at most $4\epsilon < 1$, which is a contradiction. Thus $A[i\_1]+A[i\_2]+A[i\_3] = 0$.

The same kind of reasoning works the other way around: if there are three indices such that $A[i\_1]+A[i\_2]+A[i\_3] = 0$, then you can find a hyperplane of weight at least $10m+3$ containing $p$.

---

Thus, if the 3-SUM conjecture is true, then you can't solve Maximum Weight Halfplane in strongly subquadratic time. In your problem you have $m=n^2$, so this would give an $\tilde{\Omega}(n^4)$ lower bound (if the reduction worked for points on an $n\times n$ grid, which unfortunately it doesn't).

> **Comments:**
> **username_0**: What is your current feeling about the hardness of my grid based problem?  
> **username_1**: @Simd I don't have a strong feeling either way, would need to think about it more.  
> **username_0**: It's a shame no one was able to improve this.  

---

