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?

Answer 2

An non-optimal answer is the following:

1. Generate all the possible k-plets of points (they are N × N-1 × … × N-k+1, so this is O(N^k) and can be done via recursion).

2. Filter this list down by eliminating all k-plets which are not enclosed in a a×b rectangle: this is a O(k N^k) at worst.

3. Find the k-plet which has the maximum weight: this is a O(k N^k-1) at worst.

Thus, this algorithm is O(k N^k).

Improving the algorithm

Step 2 can be integrated in step 1 by stopping the branch recursion when a set of points is already too large. This does not change the need to scan the element at least once, but it can reduce the number significantly: think of cases where there are no solutions because all points are separated more than the size of the rectangle, that can be found in O(N²).

Also, the permutation generator in step 1 can be made to return the points in order by x or y coordinate, by pre-sorting the point array correspondingly. This is useful because it lets us discard a bunch of more possibilities up front. Suppose the array is sorted by y coordinate, so the k-plets returned will be ordered by y coordinate. Now, supposing we are discarding a branch because it contains a point whose y coordinate is outside the max rectangle, we can also discard all the next sibling branches because their y coordinate will be more than of equal to the current one which is already out of bounds.

This adds O(n log n) for the sort, but the improvement can be quite significant in many cases -- again, when there are many outliers. The coordinate should be chosen corresponding to the minimum rectangle side, divided by the corresponding side of the 2D field -- by which I mean the maximum coordinate minus the minimum coordinate of all points.

Finally, if all the points lie within an a×b rectangle, then the algorithm performs as O(k N^k) anyways. If this is a concrete possibility, it should be checked, an easy O(N) loop, and if so then it's enough to return the points with the top N weights, which is also O(N).