Tight Hardness Results for Maximum Weight Rectangles
From MaRDI portal
Publication:4598221
DOI10.4230/LIPIcs.ICALP.2016.81zbMath1388.68080arXiv1602.05837OpenAlexW2963677308MaRDI QIDQ4598221
Nishanth Dikkala, Christos Tzamos, Artūrs Bačkurs
Publication date: 19 December 2017
Full work available at URL: https://arxiv.org/abs/1602.05837
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (8)
Unnamed Item ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Minimum membership covering and hitting ⋮ Smallest \(k\)-enclosing rectangle revisited ⋮ Smallest k-enclosing rectangle revisited ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry
This page was built for publication: Tight Hardness Results for Maximum Weight Rectangles
