# k-enclosing rectangle in two-colored point set

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?

• 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 ? – Vince May 15 at 8:18
• 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! – sousben May 15 at 8:59
• Also, in terms of literature search, try range trees(en.wikipedia.org/wiki/Range_tree) and range queries/orthogonal range searching. – BearAqua May 15 at 16:25
• 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. – BearAqua May 15 at 16:32
• 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. – BearAqua May 15 at 23:17

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))$$.
• 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$. – Vince May 15 at 12:16