My problem is: we have $N$ points in a 2D space, each point has a positive weight. Given a query consisting of two real numbers $a,b$ and one integer $k$, find the position of a rectangle of size $a \times b$, with edges are parallel to axes, so that the sum of weights of top-$k$ points, i.e. $k$ points with highest weights, covered by the rectangle is maximized?
Any suggestion is appreciated.
P.S.: There are two related problems, which are already well-studied:
- Maximum region sum: find the rectangle with the highest total weight sum. Complexity: $O(N\log N)$.
- top-$k$ query for orthogonal ranges: find top-$k$ points in a given rectangle. Complexity: $O(\log^2 N + k)$.