$\renewcommand{ \Re}{ { \rm I\!\hspace{ -0.025em} R}} \newcommand{ \eps}{ { \varepsilon}} \newcommand{ \SetX}{ \mathsf{ X}} \newcommand{ \VorX}[1]{ \mathcal{ V} \pth{ #1}} \newcommand{ \Polygon}{ \mathsf{ P}} \newcommand{ \Space}{ \overline{ \mathsf{ m}}} \newcommand{ \pth}[2][\!]{ #1\left({ #2}\right)}$ We revisit the problem of computing Fr\'echet distance between polygonal curves under $L_1$, $L_2$, and $L_\infty$ norms, focusing on discrete Fr\'echet distance, where only distance between vertices is considered. We develop efficient algorithms for two natural classes of curves. In particular, given two polygonal curves of $n$ vertices each, a $\eps$-approximation of their discrete Fr\'echet distance can be computed in roughly $O(n\kappa^3\log n/\eps^3)$ time in three dimensions, if one of the curves is \emph{ $\kappa$-bounded}. Previously, only a $\kappa$-approximation algorithm was known. If both curves are the so-called \emph{ \backbone~curves}, which are widely used to model protein backbones in molecular biology, we can $\eps$-approximate their Fr\'echet distance in near linear time in two dimensions, and in roughly $O(n^{ 4/3}\log nm)$ time in three dimensions. In the second part, we propose a pseudo--output-sensitive algorithm for computing Fr\'echet distance exactly. The complexity of the algorithm is a function of a quantity we call the \emph{ \bwnumber{ }}, which is quadratic in the worst case, but tends to be much smaller in practice.
Categories: cs.CG