## Abstract

Given a set P of n points in R^{d}, 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(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és et al., J. Alg., 2009; Dobkin et al., J. Comput. Syst. Sci., 1996].

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

Pages | 151-156 |

Number of pages | 6 |

State | Published - 2013 |

Externally published | Yes |

Event | 25th Canadian Conference on Computational Geometry, CCCG 2013 - Waterloo, Canada Duration: Aug 8 2013 → Aug 10 2013 |

### Other

Other | 25th Canadian Conference on Computational Geometry, CCCG 2013 |
---|---|

Country | Canada |

City | Waterloo |

Period | 8/8/13 → 8/10/13 |

## ASJC Scopus subject areas

- Geometry and Topology
- Computational Mathematics