Reduction from CNF-SAT to Frechet Distance
Jump to navigation
Jump to search
FROM: CNF-SAT TO: Frechet Distance
Description
Implications
If: to-time: $O({2}^{({2}-\epsilon)}$ for any $\epsilon > {0}$
Then: from-time: $O({2}^{({1}-\delta/{2})N}$ where $N$ is s.t there are $n=\tilde{O}({2}^{N/2})$ vertices on each curve
Year
2014
Reference
Karl Bringmann, Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails