Frechet Distance: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Frechet Distance (Frechet Distance)}} == 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 == <pre>n: length of first curve m: length of second curve</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FRO...") |
No edit summary |
||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
n: length of first curve | |||
m: length of second curve | |||
m: length of second curve | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Revision as of 12:04, 15 February 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 |