Find a region with maximum sum of top-K points

Question

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 x 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: NlogN.
• top-K query for orthogonal ranges: find top-k points in a given rectangle. Complexity: O(log(N)^2+k).

Answer 1

You can reduce this problem into finding two points in the rectangle: rightmost and topmost. So effectively you can select every pair of points and calculate the top-k weight (which according to you is O(log(N)^2+k)). Complexity: O(N^2*(log(N)^2+k)).

Now, given two points, they might not form a valid pair: they might be too far or one point may be right and top of the other point. So, in reality, this will be much faster.

My guess is the optimal solution will be a variation of maximum region sum problem. Could you point to a link describing that algorithm?