## Abstract

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∩P}w(p). We describe algorithms for this problem in two dimensions that run in the worst case in O(^{n2}) 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(^{n2}lgn) (Cortés et al., 2009 [9]; Dobkin et al., 1996 [10]). Although the O(^{n2}) 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}/^{lgd}n)(^{lglgn)O(1)}) time; (3) it is unlikely that the Maximum-Weight Box problem can be solved in less than nd/^{2} time (ignoring logarithmic factors) with current knowledge about Klee's Measure problem.

Original language | English (US) |
---|---|

Pages (from-to) | 437-445 |

Number of pages | 9 |

Journal | Information Processing Letters |

Volume | 114 |

Issue number | 8 |

DOIs | |

State | Published - Aug 2014 |

Externally published | Yes |

## Keywords

- Adaptive algorithms
- Computational geometry
- Divide-summarize-and-conquer
- Klee's Measure problem
- Maximum box

## ASJC Scopus subject areas

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications

## Fingerprint

Dive into the research topics of 'Maximum-weight planar boxes in O (^{n2}) time (and better)'. Together they form a unique fingerprint.