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?