4
$\begingroup$

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:

enter image description here

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Tassle
    Dec 21, 2023 at 19:04
  • $\begingroup$ can you clarify the link with 3SUM $\endgroup$
    – kodlu
    Dec 21, 2023 at 19:31
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Dec 21, 2023 at 19:34
  • $\begingroup$ @D.W. The linked algorithm runs in $O(n^4)$ time and looks correct. It is missing a proof however. $\endgroup$
    – Simd
    Dec 21, 2023 at 19:40
  • $\begingroup$ @Simd, Yup, I know, I did look at it. I think my question remains relevant. $\endgroup$
    – D.W.
    Dec 22, 2023 at 0:05

1 Answer 1

2
+50
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What is your current feeling about the hardness of my grid based problem? $\endgroup$
    – Simd
    Dec 22, 2023 at 17:23
  • $\begingroup$ @Simd I don't have a strong feeling either way, would need to think about it more. $\endgroup$
    – Tassle
    Dec 23, 2023 at 22:49
  • $\begingroup$ It's a shame no one was able to improve this. $\endgroup$
    – Simd
    Dec 30, 2023 at 9:05

Your Answer

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

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