Maximum-weight planar boxes in O (ⁿ²) time (and better)

Given a set P of n points in ^Rd, 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 σ _p∈B∩Pw(p). We describe algorithms for this problem in two dimensions that run in the worst case in O(ⁿ²) 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 Θ(lgn) on the previously known worst-case complexity for these problems, O(ⁿ²lgn) (Cortés et al., 2009 [9]; Dobkin et al., 1996 [10]). Although the O(ⁿ²) result can be deduced from new results on Klee's Measure problem (Chan, 2013 [7]), 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( ^nd) 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((^nd/^lgdn)(^lglgn)O(1)) time; (3) it is unlikely that the Maximum-Weight Box problem can be solved in less than nd/² time (ignoring logarithmic factors) with current knowledge about Klee's Measure problem.