2
$\begingroup$

I was asked to write an algorithm for the following problem, and discuss complexity:

  • There are p points of two colours, black and white, in an n*m grid.

  • Any cell in the grid can contain 0 or more points, of any colour.

  • We are looking for an axis aligned rectangle, having (0,0) as a corner, containing k black points, and maximizing the number of white points in it.

It was mentioned that this problem is famous and I can use any online resource.

So far, the closest I have found is this paper, which deals with finding exact colored k-enclosing rectangles, that don't necessarily have the origin as a vertex.

Maybe someone here will be able to point me to some resources that discuss this version of the problem?

$\endgroup$
  • 1
    $\begingroup$ hint: just imagine you want to build two n*m arrays $B$ and $W$. $B[i,j]$ and $W[i,j]$ are respectively the total number of black and white points in the rectangle (left=0, up=0, right=i, down=j). How would you proceed ? $\endgroup$ – Vince May 15 at 8:18
  • $\begingroup$ Thanks, that's exactly what I had in mind! My initial thought was to first sort the points by x and y coordinates, then write a function that accumulates the number of B and W found for any smaller or equal x and y. I believe the initialization would be in O(p log p + m*n). I would also update a list of size b (number of black points) which stores the best coordinates for a given k - so that the cost of finding the best coordinates for a given k would be in O(1). That said, there may be more optimal solutions out there! $\endgroup$ – sousben May 15 at 8:59
  • 1
    $\begingroup$ Also, in terms of literature search, try range trees(en.wikipedia.org/wiki/Range_tree) and range queries/orthogonal range searching. $\endgroup$ – BearAqua May 15 at 16:25
  • $\begingroup$ Also, a good runtime should not be dependent on $m,n$. Let $(x,y)$ be the farthest point to bottom right, any $O(mn)$-time solution can be turned into an $O(xy)$-time one. $\endgroup$ – BearAqua May 15 at 16:32
  • $\begingroup$ If you sweep from left to right, notice how the height of all rectangles containing exactly $k$ white points is monotonically decreasing. You can use this to do further pruning. $\endgroup$ – BearAqua May 15 at 23:17
1
$\begingroup$

Ok as you have a working solution but seem concerned by optimization, I will detail here how to do it very efficiently. I assume that your rectangle has to follow the discretized grid (I now have a doubt on it reading your question).

Let's build 2 $n \times m$ count arrays $NB$ and $NW$ which are the number of respectively black and white points in each cell. You can fill these arrays in $O(p)$ as you just have to consider any point and decide which value of the array you increment.

Then you build the 2 $n \times m$ accumulator arrays $RB$ and $RW$. $RB[i, j]$ and $RW[i, j]$ are the number of respectively black and white points in the rectangle (left=0, up=0, right=$j$, down=$i$). You can fill these arrays with a very simple DP using $NW$ and $NR$, in $O(nm)$. Note that computing row after row, and in the row looping on elements, you can break the latter loop whenever $RB > k$.

The overall time complexity will be $O(max(p, nm))$.

$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer, but I am not sure I agree with the last step. Why not create an array that stores the best_ij for each possible value of k at the same time as we build the accumulator arrays? That would allow to find the best_ij in O(1). Also, we are not looking for all possible best_ij but only one, but that doesn't make a big diff $\endgroup$ – sousben May 15 at 10:05
  • 1
    $\begingroup$ Yes you are totally right, I will remove this. In fact you can even can break the computation of any row of $RB$ when it grows over $k$. $\endgroup$ – Vince May 15 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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