Maximum-Weight Planar Boxes in O(n 2 ) Time (and Better)
Author
dc.contributor.author
Barbay, Jérémy
Author
dc.contributor.author
Chan, Timothy M.
es_CL
Author
dc.contributor.author
Navarro, Gonzalo
es_CL
Author
dc.contributor.author
Pérez Lantero, Pablo
Admission date
dc.date.accessioned
2014-12-11T15:34:54Z
Available date
dc.date.available
2014-12-11T15:34:54Z
Publication date
dc.date.issued
2013
Cita de ítem
dc.identifier.citation
Information Processing Letters 114 (2014) 437–445
en_US
Identifier
dc.identifier.other
dx.doi.org/10.1016/j.ipl.2014.03.007
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/126523
General note
dc.description
Articulo de publicacion SCOPUS
en_US
Abstract
dc.description.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.