Fine-grained complexity theory: conditional lower bounds for computational geometry

DOI10.1007/978-3-030-80049-9_6OpenAlexW3181333534MaRDI QIDQ2117766FDOQ2117766

Karl Bringmann

Publication date: 22 March 2022

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

zbMATH Keywords

computational geometryfine-grained complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a class of \(O(n^ 2)\) problems in computational geometry
• On the complexity of \(k\)-SAT
• A new algorithm for optimal 2-constraint satisfaction and its implications
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Computing the Discrete Fréchet Distance in Subquadratic Time
• Approximability of the discrete Fréchet distance
• Approximating the Fréchet distance for realistic curves in near linear time
• Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
• Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees
• More Applications of the Polynomial Method to Algorithm Design
• Polyline simplification has cubic complexity
• An improved approximation algorithm for the discrete Fréchet distance
• Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability
• Hardness of approximate nearest neighbor search
• Tight Hardness Results for Maximum Weight Rectangles
• Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
• ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
• Fine-Grained Complexity Theory (Tutorial)
• SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension

Cited In (3)

• Title not available (Why is that?)
• Density-based clustering in MapReduce with guarantees on parallel time, space, and solution quality
• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension

This page was built for publication: Fine-grained complexity theory: conditional lower bounds for computational geometry

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