Maximum rectangle for very special matrices

Question

While working on the image processing problem, I encountered the following problem: in a unit square there are n points with coordinates $ x_i $ and $ y_i $, each of which has a positive or negative weight $ w_i $. Find the rectangle so that the sum of all the weights of these points lying inside the rectangle is positive and maximum.

By defining the correct grid, the problem can be rephrased as finding the submatrix in the n-on-n matrix A, the sum of the elements of which is maximal. This is also known as the “maximum sub-problem” and has been discussed earlier on SO. While the brute force approach has an O (n ^ 5) runtime, there is a peculiar complex solution with O (n ^ 3) runtime. It uses a solution for the corresponding one-dimensional problem, called the “maximum subaram problem” , with an O (n) runtime.

I implemented both algorithms in R and can solve 100 seconds of points in a few seconds. But with thousands of points, it will be too slow, perhaps even when outsourcing loops to some fortran or C code.

Now let's look at the matrix A. If we assume (without loss of generality) that all points have different x- or y-coordinates, then A has a special form: each row and column A has exactly one non-element -zero. For matrices with this special property, I assume that there must be an algorithm that performs the task in O (n ^ 2), or even better.

Here is an example with the addition of an optimal rectangle:

set.seed(723) N <- 50; w <- rnorm(N) x <- runif(N); y <- runif(N) clr <- ifelse (w >= 0, "blue", "red") plot(x, y, pch = 20, col = clr, xlim = c(0, 1), ylim = c(0, 1)) rect(0.075, 0.45, 0.31, 0.95, border="gray") 

You see what may be red, i.e. negative indicates an optimal rectangle. It also shows that it is not enough to solve one-dimensional cases for x- and y-coordinates.

I will translate the standard solution into Fortran, but I would really like to have a more efficient algorithm.

Answer 1

These guys (found on the wiki page) claim to have a simpler cube solution for the two-dimensional case. It may be the one you already know about.

Answer 2

See the accepted answer for "Maximum summary rectangle in a sparse matrix". For an nxn matrix with m nonzero elements, the decision there takes O (nm log n) time. So, for you, since you have exactly n nonzero elements, this will give O (n ^ 2 log n) time. You will probably be able to handle cases with n 50 times larger or larger than the standard O solution (n ^ 3).

Answer 3

The best I can do is O (n ^ 2 log n).

If we look at n + 1, we select 2 calls made by the Kadan algorithm to the 2D Kadan 1D algorithm at the input of your type, all but O (n) consecutive pairs are on 1D arrays that differ by only one element. I am going to present a variant of Kadane 1D with division and victory; by caching the results of each recursive call, it is necessary to redefine only O (log n), which include the changed element of the array, reducing the (amortized) runtime of the inner loop from Theta (n) to Theta (log n).

 def maxsubarray(arr, a, b): # this function returns a 4-tuple # element 0 is the max over intervals of the form [i, j) # element 1 is the max over intervals of the form [i, b) # element 2 is the max over intervals of the form [a, j) # element 3 is the max over intervals of the form [a, b), ie, sum(arr[a:b]) n = b - a if n == 0: return (0, 0, 0, 0) elif n == 1: x = arr[a] y = max(x, 0) return (y, y, y, x) else: m = a + n // 2 l = maxsubarray(arr, a, m) r = maxsubarray(arr, m, b) return (max(l[0], r[0], l[1] + r[2]), max(r[1], l[1] + r[3]), max(l[2], l[3] + r[2]), l[3] + r[3])