  The \emph{Fr\'echet distance} is a well studied similarity measures between
curves. The \emph{discrete Fr\'echet distance} is an analogous similarity
measure, defined for a sequence $A$ of $m$ points and a sequence $B$ of $n$
points, where the points are usually sampled from input curves. In this paper
we consider a variant, called the \emph{discrete Fr\'echet distance with
shortcuts}, which captures the similarity between (sampled) curves in the
presence of outliers. For the \emph{two-sided} case, where shortcuts are
allowed in both curves, we give an $O((m^{2/3}n^{2/3}+m+n)\log^3 (m+n))$-time
algorithm for computing this distance. When shortcuts are allowed only in one
noise-containing curve, we give an even faster randomized algorithm that runs
in $O((m+n)^{6/5+\varepsilon})$ expected time, for any $\varepsilon>0$.
  Our techniques are novel and may find further applications. One of the main
new technical results is: Given two sets of points $A$ and $B$ and an interval
$I$, we develop an algorithm that decides whether the number of pairs $(x,y)\in
A\times B$ whose distance ${\rm dist}(x,y)$ is in $I$, is less than some given
threshold $L$. The running time of this algorithm decreases as $L$ increases.
In case there are more than $L$ pairs of points whose distance is in $I$, we
can get a small sample of pairs that contains a pair at approximate median
distance (i.e., we can approximately "bisect" $I$). We combine this procedure
with additional ideas to search, with a small overhead, for the optimal
one-sided Fr\'echet distance with shortcuts, using a very fast decision
procedure. We also show how to apply this technique for approximating distance
selection (with respect to rank), and for computing the semi-continuous
Fr\'echet distance with one-sided shortcuts.
