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?
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 &gt; k$. 

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