Maximum-Weight Planar Boxes in O(n 2 ) Time (and Better)

Abstract

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 P p∈B∩P w(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 Θ(log n) on the best worst-case complexity previously known for these problems, O(n 2 lg n) [Cort´es 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 the Klee’s Measure problem [Chan, 2013], it is a more direct and simplified (nontrivial) solution, which further provides smaller running times on specific classes on instances.