Is there a lower bound for the problem of finding the best straight line partition

Question

I recently asked the following algorithms question on another site. 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:

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$.

Answer 1

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