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.