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 conferencePaperpeer-review

Abstract

Given a set P of n points in Rd, where each point p of P is associated with a weight ω(p) (positive or negative), the Maximum-Weight Box problem consists in finding an axis-aligned box B maximizing σpεB∩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 θ(log n) on the best worst-case complexity previously known for these problems, O(n2 lg n) [Cortés et al., J. Alg., 2009; Dobkin et al., J. Comput. Syst. Sci., 1996].

Original languageEnglish (US)
Pages151-156
Number of pages6
StatePublished - 2013
Externally publishedYes
Event25th Canadian Conference on Computational Geometry, CCCG 2013 - Waterloo, Canada
Duration: Aug 8 2013Aug 10 2013

Other

Other25th Canadian Conference on Computational Geometry, CCCG 2013
CountryCanada
CityWaterloo
Period8/8/138/10/13

ASJC Scopus subject areas

  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Maximum-weight planar boxes in O(n<sup>2</sup>) time (and better)'. Together they form a unique fingerprint.

Cite this