Maximum-Weight Planar Boxes in O(n^2) Time (and Better)
Jérémy Barbay, Timothy Chan, Gonzalo Navarro, and Pablo Pérez-Lantero
Given a set P of n points in R^d, where
each point p
of P is associated with a weight w(p) (positive or negative), the
Maximum-Weight Box problem consists in finding an axis-aligned box B
maximizing sum { w(p), p in intersection(B,P) }.
We describe algorithms for this problem in two dimensions that run in the
worst case in O(n^2) time, and much less on more specific classes of
instances.
In particular, these results imply similar ones for the Maximum
Bichromatic Discrepancy Box problem.
These improve by a factor of Theta(log n) on the best worst-case
complexity previously known for these problems, O(n^2 lg n) [Cortŕs et
al., J. Alg., 2009; Dobkin et al., J. Comput. Syst. Sci., 1996].