|
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 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) [Cortes et al., J. Alg., 2009; Dobkin et al., J. Comput. Syst. Sci., 1996]. |
