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

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