  $\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.
