###
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].