Frechet Distance: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
n: length of first curve | $n$: length of first curve | ||
m: length of second curve | $m$: length of second curve | ||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 08:27, 10 April 2023
Description
Intuitively, the (continuous) Fréchet distance of two curves $P, Q$ is the minimal length of a leash required to connect a dog to its owner, as they walk along $P$ or $Q$, respectively, without backtracking.
Parameters
$n$: length of first curve
$m$: length of second curve
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| CNF-SAT | 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 |
2014 | https://people.mpi-inf.mpg.de/~kbringma/paper/2014FOCS.pdf | link |