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

Jérémy Barbay, Timothy M. Chan, Gonzalo Navarro, Pablo Pérez-Lantero

Research output: Contribution to journalArticlepeer-review

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∩Pw(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(n2lgn) (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/lgdn)(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 languageEnglish (US)
Pages (from-to)437-445
Number of pages9
JournalInformation Processing Letters
Volume114
Issue number8
DOIs
StatePublished - Aug 2014
Externally publishedYes

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 (<sup>n2</sup>) time (and better)'. Together they form a unique fingerprint.

Cite this