Tight hardness results for maximum weight rectangles

DOI10.4230/LIPICS.ICALP.2016.81MaRDI QIDQ4598221zbMATH OpenOpenAlexFDO

Authors Artūrs Bačkurs, Nishanth Dikkala, Christos Tzamos

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1602.05837

zbMATH Keywords

hardness in Pmaximum rectangles

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Given $n$ weighted points (positive or negative) in $d$ dimensions, what is the axis-aligned box which maximizes the total weight of the points it contains? The best known algorithm for this problem is based on a reduction to a related problem, the Weighted Depth problem [T. M. Chan, FOCS'13], and runs in time $O(n^d)$. It was conjectured [Barbay et al., CCCG'13] that this runtime is tight up to subpolynomial factors. We answer this conjecture affirmatively by providing a matching conditional lower bound. We also provide conditional lower bounds for the special case when points are arranged in a grid (a well studied problem known as Maximum Subarray problem) as well as for other related problems. All our lower bounds are based on assumptions that the best known algorithms for the All-Pairs Shortest Paths problem (APSP) and for the Max-Weight k-Clique problem in edge-weighted graphs are essentially optimal.

Recommendations

• Maximum-weight planar boxes in \(O(n^2)\) time (and better)
• On the largest empty axis-parallel box amidst \(n\) points
• Maximum box problem on stochastic points
• Maximum box problem on stochastic points
• The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions

Cited in

(12)

• Smallest \(k\)-enclosing rectangle revisited
• Fine-grained complexity theory: conditional lower bounds for computational geometry
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• From circuit complexity to faster all-pairs shortest paths
• Smallest k-enclosing rectangle revisited
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Minimum membership covering and hitting
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• On the fine-grained complexity of parity problems
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Algorithms and hardness for multidimensional range updates and queries

This page was built for publication: Tight hardness results for maximum weight rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598221)