Fine-grained complexity theory: conditional lower bounds for computational geometry
From MaRDI portal
Publication:2117766
DOI10.1007/978-3-030-80049-9_6OpenAlexW3181333534MaRDI QIDQ2117766
Publication date: 22 March 2022
Full work available at URL: https://arxiv.org/abs/2110.10283
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the Fréchet distance for realistic curves in near linear time
- Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees
- An improved approximation algorithm for the discrete Fréchet distance
- On a class of \(O(n^ 2)\) problems in computational geometry
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Approximability of the discrete Fréchet distance
- Tight Hardness Results for Maximum Weight Rectangles
- COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
- Fine-Grained Complexity Theory (Tutorial)
- ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
- Hardness of approximate nearest neighbor search
- SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
- Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability
- More Applications of the Polynomial Method to Algorithm Design
- Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
- Computing the Discrete Fréchet Distance in Subquadratic Time
- Polyline simplification has cubic complexity
- On the complexity of \(k\)-SAT
This page was built for publication: Fine-grained complexity theory: conditional lower bounds for computational geometry
