Maximizing Weighted Dominance in the Plane

Let P be a set of n weighted points, Q be a set of m unweighted points in the plane, and k a non-negative integer. We consider the problem of computing a subset Q'⊆ Q with size at most k such that the sum of the weights of the points of P dominated by at least one point in the set Q' is maximized. A point q in the plane dominates another point p if and only if x(q)≥ x(p) and y(q)≥ y(p), and at least one inequality is strict. We present a solution to the problem that takes O(n + m)-space and O(k min+m, n/k+m²log m)-time. We (conditionally) improve upon the existing result (the bounds of our solution are interesting when m= o(√n)). Moreover, we also present a simple algorithm solving the problem in O(km²+nlog m)-time and $O(n+m)$-space. The bounds of the algorithm are interesting when m= o(√n).