Maximum-weight planar boxes in \(O(n^2)\) time (and better)
From MaRDI portal
Publication:2448119
DOI10.1016/j.ipl.2014.03.007zbMath1296.68073OpenAlexW2150045034MaRDI QIDQ2448119
Timothy M. Chan, Jérémy Barbay, Gonzalo Navarro, Pablo Pérez-Lantero
Publication date: 30 April 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2014.03.007
adaptive algorithmscomputational geometryKlee's measure problemdivide-summarize-and-conquermaximum box
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (13)
Dynamic Minimum Bichromatic Separating Circle ⋮ Dynamic minimum bichromatic separating circle ⋮ Faster algorithms for largest empty rectangles and boxes ⋮ Variations of largest rectangle recognition amidst a bichromatic point set ⋮ Hierarchical design of fast minimum disagreement algorithms ⋮ Planar maximum-box problem revisited ⋮ New results on the coarseness of bicolored point sets ⋮ Unnamed Item ⋮ Minimum membership covering and hitting ⋮ Maximum box problem on stochastic points ⋮ Smallest \(k\)-enclosing rectangle revisited ⋮ Smallest k-enclosing rectangle revisited ⋮ Hierarchical Design of Fast Minimum Disagreement Algorithms
Cites Work
- Computing optimal islands
- On the coarseness of bicolored point sets
- A (slightly) faster algorithm for Klee's measure problem
- The maximum box problem and its application to data analysis
- Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning
- Bichromatic separability with two boxes: A general approach
- The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
- New Upper Bounds in Klee’s Measure Problem
- On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences
This page was built for publication: Maximum-weight planar boxes in \(O(n^2)\) time (and better)
