###
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 is to find 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(lg n)* on the previously known
worst-case complexity for these problems, *O(n^2 lg n)* [Cortŕs et
al., J. Alg., 2009; Dobkin et al., J. Comput. Syst. Sci., 1996].
Although the *O(n^2)* result can be deduced from new results on Klee's
Measure problem [Chan, Proc. FOCS 2013], it is a more direct and simplified
(non-trivial) solution. We exploit the connection with Klee's Measure problem
to further show that (1) the Maximum-Weight Box problem can be solved in
*O(n^d)* time for any constant *d ≥ 2*; (2) if the weights are
integers bounded by *O(1)* in absolute values, or weights are +1 and
-∞ (as in the Maximum Bichromatic Discrepancy Box problem), the
Maximum-Weight Box problem can be solved in *O((n^d / lg^d n)(lg lg n)
O(1))* time; (3) it is unlikely that the Maximum-Weight Box problem can be
solved in less than *n^(d/2)* time (ignoring logarithmic factors) with
current knowledge about Klee's Measure problem.