The Discrete and the Semi-Continuous Fr\'echet Distance with Shortcuts
Rinat Ben Avraham% \thanks{School of Computer Science
Tel Aviv 69978
Omrit Filtser% \thanks{Department of Computer Science
Beer-Sheva 84105
Haim Kaplan% \thanks{School of Computer Science
Matthew J. Katz% \thanks{Department of Computer Science
Micha Sharir% \thanks{School of Computer Science
Tel~Aviv 69978
The Fr\'echet distance is a well studied similarity measure between curves. The discrete Fr\'echet distance is an analogous similarity measure, defined for two sequences of $m$ and $n$ points, where the points are usually sampled from input curves. We consider a variant, called the discrete Fr\'echet distance with shortcuts, which captures the similarity between (sampled) curves in the presence of outliers. When shortcuts are allowed only in one noise-containing curve, we give a randomized algorithm that runs in $O((m+n)^{6/5+\eps})$ expected time, for any $\eps>0$. When shortcuts are allowed in both curves, we give an $O((m^{2/3}n^{2/3}+m+n)\log^3 (m+n))$-time deterministic algorithm. We also consider the semi-continuous Fr\'echet distance with one-sided shortcuts, where we have a sequence of $m$ points and a polygonal curve of $n$ edges, and shortcuts are allowed only in the sequence. We show that this problem can be solved in randomized expected time $O((m+n)^{2/3}m^{2/3}n^{1/3}\log(m+n))$. 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$ in the plane and an interval $I$, we develop an algorithm that decides whether the number of pairs $(x,y)\in A\times B$ whose distance ${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 a somewhat more involved variant of this technique is used in the solution of the semicontinuous Fr\'echet distance with one-sided shortcuts. In general, the new technique can apply to optimization problems for which the decision procedure is very fast but standard techniques like parametric search makes the optimization algorithm substantially slower.
abstract1.tex
\begin{abstract}
The \emph{Fr\'echet distance} is a well studied similarity measure between
curves. The \emph{discrete Fr\'echet distance} is an analogous similarity measure,
defined for two sequences of $m$ and $n$ points, where
the points are usually sampled from input curves. 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. When shortcuts are allowed only in one noise-containing
curve, we give a randomized algorithm that runs in $O((m+n)^{6/5+\eps})$
expected time, for any $\eps>0$. When shortcuts are allowed in
both curves, we give an $O((m^{2/3}n^{2/3}+m+n)\log^3 (m+n))$-time deterministic algorithm.

We also consider the semi-continuous Fr\'echet
distance with one-sided shortcuts, where we have a sequence of $m$ points and a polygonal curve of $n$ edges, and shortcuts are allowed only in the sequence. We show that this problem can be solved in randomized expected time $O((m+n)^{2/3}m^{2/3}n^{1/3}\log(m+n))$.

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$ in the plane 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 a somewhat more involved variant of this technique is used in the solution of the semicontinuous Fr\'echet distance with one-sided shortcuts. In general, the new technique
can apply to optimization problems for which the decision procedure
is very fast but standard techniques like parametric search makes
the optimization algorithm substantially slower.

\end{abstract}

discrete_shortcuts.tex
\section{Preliminaries}
We now give a formal definition of the discrete Fr\'echet distance and its variants.

Let $A=(a_{1},\ldots,a_{m})$ and $B=(b_{1},\ldots,b_{n})$ be two
sequences of $m$ and $n$ points, respectively, in the plane. Let $G(V,E)$ denote a graph whose vertex set is $V$ and edge set is $E$, and let $\|\cdot\|$ denote the Euclidean norm.
Fix a distance $\delta>0$, and define the following three directed graphs $G_\delta=G(A\times B, E_{\delta})$, $G_\delta^-=G(A\times B, E_{\delta}^-)$, and $G_\delta^+=G(A\times B, E_{\delta}^+)$, where
\begin{align*}
E_{\delta}= & \left\{ \Bigr((a_{i},b_{j}),(a_{i+1},b_{j})\Bigl)\:\middle|\,\|a_{i}-b_{j}\|,\;\|a_{i+1}-b_{j}\|\le\delta\right\} \bigcup\\
 & \left\{ \Bigr((a_{i},b_{j}),(a_{i},b_{j+1})\Bigl)\:\middle|\,\|a_{i}-b_{j}\|,\;\|a_{i}-b_{j+1}\|\le\delta\right\},\\%%%%%%%%%%%%%%
E_{\delta}^{-}= & \left\{ \Bigr((a_{i},b_{j}),(a_{k},b_{j})\Bigl)\:\middle|\, k>i,\,\|a_{i}-b_{j}\|,\;\|a_{k}-b_{j}\|\le\delta\right\} \bigcup\\
 & \left\{ \Bigr((a_{i},b_{j}),(a_{i},b_{j+1})\Bigl)\:\middle|\,\|a_{i}-b_{j}\|,\;\|a_{i}-b_{j+1}\|\le\delta\right\},%%%%%%%%%%%%%%%%%%
\end{align*}
\begin{align*}
E_{\delta}^{+}= & \left\{ \Bigr((a_{i},b_{j}),(a_{k},b_{j})\Bigl)\:\middle|\, k>i,\,\|a_{i}-b_{j}\|,\;\|a_{k}-b_{j}\|\le\delta\right\} \bigcup\\
 & \left\{ \Bigr((a_{i},b_{j}),(a_{i},b_{l})\Bigl)\:\middle|\, l>j,\,\|a_{i}-b_{j}\|,\;\|a_{i}-b_{l}\|\le\delta\right\}.
\end{align*}
For each of these graphs we say
that a position $(a_{i},b_{j})$ is a \emph{reachable}
position if $(a_{i},b_{j})$ is reachable from $(a_{1},b_{1})$ in the respective graph.
Then the discrete Fr\'echet distance (DFD for short) $\delta_F^{*}(A,B)$ is the smallest $\delta>0$
for which $(a_{m},b_{n})$ is a reachable position in $G_\delta$.
Similarly, the one-sided Fr\'echet distance with shortcuts (one-sided DFDS for short) $\delta_F^{-}(A,B)$ is the smallest $\delta>0$
for which $(a_{m},b_{n})$ is a reachable position in $G_\delta^-$, and the two-sided Fr\'echet distance with shortcuts (two-sided DFDS for short) $\delta_F^{+}(A,B)$ is the smallest $\delta>0$
for which $(a_{m},b_{n})$ is a reachable position in $G_\delta^+$.


%\begin{figure}[htp]
%  \centering


 % \begin{subfigure}[b]{0.3\textwidth}{\label{figur:1}\includegraphics[width=60mm]{figures/matrix}}\end{subfigure}

 % \begin{subfigure}[b]{0.3\textwidth}{\label{figur:2}\includegraphics[width=60mm]{figures/sparse}}\end{subfigure}

 % \begin{subfigure}[b]{0.3\textwidth}{\label{figur:3}\includegraphics[width=60mm]{figures/discrete}}\end{subfigure}



%\end{figure}



\section{Decision procedure for the one-sided DFDS}

\label{sec:DFDS1} We first consider the corresponding decision problem.
That is, given a value $\delta>0$, we wish to decide whether $\delta_F^{-}(A,B)\le\delta$ (we ignore the issue of
discrimination between the cases of strict inequality and equality, in the decision procedures of both the one-sided variant and the two-sided variant, since this will be handled in the optimization procedures, described later).

Let $M$ be the matrix whose rows correspond to the elements of $A$ and
whose columns correspond to the elements of $B$ and $M_{i,j}=1$ if
$\|a_{i}-b_{j}\|\le\delta$, and $M_{i,j}=0$ otherwise. Consider
first the DFD variant (no shortcuts allowed), in which,
at each move, exactly one of the frogs has to jump to the next
point. Suppose that $(a_{i},b_{j})$ is a reachable position of the
frogs. Then, necessarily, $M_{i,j}=1$. If $M_{i+1,j}=1$ then the
next move can be an {\em upward move} in which the $A$-frog moves
from $a_{i}$ to $a_{i+1}$, and if $M_{i,j + 1} = 1$ then the next
move can be a {\em right move} in which the $B$-frog moves from
$b_{j}$ to $b_{j+1}$. It follows that to  determine whether
$\delta_F^{*}(A,B)\le\delta$, we need to determine whether there is
a \emph{right-upward staircase} of ones in $M$ that starts at
$M_{1,1}$, ends at $M_{m,n}$, and consists of a sequence of
interweaving upward moves and right moves (see
Figure~\ref{fig:staircase}(a)).

\begin{figure*}[htp]
\centering

\begin{tabular}{ccc}
\includegraphics[scale=0.8]{staircase3_a.pdf} & \hspace{0.5cm}
\includegraphics[scale=0.8]{staircase3_c.pdf} & \hspace{0.5cm}
\includegraphics[scale=0.8]{staircase3_b.pdf} \\
(a) & (b) & (c)
\end{tabular}
\vspace{-0.5cm}
%\end{figure}
%\centering \includegraphics[scale=0.8]{figures/staircase3.pdf}
\centering \caption{\small (a) A right-upward staircase (for DFD with no simultaneous jumps). (b) A semi-sparse
staircase (for the one-sided DFDS). (c) A sparse
staircase (for the two-sided DFDS).}
\label{fig:staircase}
\end{figure*}


In the
one-sided version of DFDS, given a
reachable position $(a_{i},b_{j})$ of the frogs, the $A$-frog can
move to any point $a_{k},k>i$, for which $M_{k,j}=1$; this is a
\emph{skipping upward move} in $M$ which starts at $M_{i,j}=1$,
skips over $M_{i+1,j},\ldots,M_{k-1,j}$ (some of which may be 0),
and reaches $M_{k,j}=1$. However, in this variant, as in the DFD variant, the $B$-frog
can only make a consecutive \emph{right move}  from $b_{j}$ to $b_{j+1}$,
provided that $M_{i,j+1}=1$ (otherwise no move of the $B$-frog is
possible at this position). Determining whether
$\delta_F^{-}(A,B)\le\delta$ corresponds to deciding whether there
is a \emph{semi-sparse staircase} of ones in $M$ that starts at
$M_{1,1}$, ends at $M_{m,n}$, and consists of an interweaving
sequence of skipping upward moves and (consecutive) right moves (see
Figure~\ref{fig:staircase}(b)).


Assume that $M_{1,1}=1$ and $M_{m,n}=1$; otherwise, we can immediately
conclude that $\delta_F^{-}(A,B)>\delta$ and terminate the decision procedure. From now on, whenever we
refer to a semi-sparse staircase, we mean a semi-sparse staircase
of ones in $M$ starting at $M_{1,1}$, as defined above, but without the requirement that it ends at $M_{m,n}$.

\begin{figure}[htbp]
\MyFrame{
\smallskip
\begin{itemize}
{\small \sf
\item $S \leftarrow \langle M_{1,1}\rangle$ \vspace{-0.3cm}
\item $i \leftarrow 1$, $j \leftarrow 1$ \vspace{-0.3cm}
\item While $(i < m$ or $j < n)$ do \vspace{-0.3cm}
    \begin{itemize}
    \item {\small \sf If (a right move is possible) then } \vspace{-0.1cm}
        \begin{itemize}
                             \item Make a right move and add position $M_{i,j+1}$ to $S$ \vspace{-0.1cm}
                             \item $j \leftarrow j+1$ \vspace{-0.2cm}
        \end{itemize}
    \item Else \vspace{-0.2cm}
        \begin{itemize}
        \item If (a skipping upward move is possible) then \vspace{-0.1cm}
                            \begin{itemize}
                                   \item Move upwards to the first (i.e., lowest) position $M_{k,j}$, with $k>i$ and $M_{k,j}=1$, and add $M_{k,j}$ to $S$ \vspace{-0.1cm}
                             \item $i\leftarrow k$ \vspace{-0.2cm}
                            \end{itemize}

        \item Else \vspace{-0.2cm}
                \begin{itemize}
                     \item Return $\delta_F^-(A,B)>\delta$ \vspace{-0.3cm}
                \end{itemize}
\end{itemize}
\end{itemize}
                  %   \ENDIF
               %\ENDIF
            %   \ENDWHILE
        \item Return $\delta_F^-(A,B)\le\delta$
}
\end{itemize}
}\caption{Decision procedure for the one-sided discrete Fr\'echet distance with shortcuts.} \label{alg:semi-sparse}
\end{figure}

The algorithm of Figure~\ref{alg:semi-sparse}, that implements the
decision procedure, constructs a semi-sparse staircase $S$ by always
making a right move if possible. The correctness of the decision
procedure is established by the following lemma.

\begin{lemma} \label{lem:one-sided}
If there exists a semi-sparse staircase that ends at
$M_{m,n}$, then $S$ also ends at $M_{m,n}$. Hence $S$ ends at $M_{m,n}$ if and only if $\delta_F^-(A,B) \le \delta$.
\end{lemma}

\begin{proof}
Let $S'$ be a semi-sparse staircase that ends at $M_{m,n}$. We think
of $S'$ as a sequence of possible positions (i.e., $1$-entries) in
$M$. Note that $S'$ has at least one position in each column of $M$,
since skipping is not allowed when moving rightwards. We claim that
for each position $M_{k,j}$ in $S'$, there exists a position
$M_{i,j}$ in $S$, such that $i \le k$. This, in particular, implies
that $S$ reaches the last column. If $S$ reaches the last column, we
can continue it and reach  $M_{m,n}$ by a sequence of skipping upward
moves (or just by one such move), so the lemma follows.

We prove the claim by induction on $j$. It clearly holds for
$j=1$ as both $S$ and $S'$ start at $M_{1,1}$. We assume then
that the claim holds for $j=\ell-1$, and establish it for $\ell$.
That is, assume that if $S'$ contains an entry $M_{k,\ell-1}$, then $S$
contains $M_{i,\ell-1}$ for some $i\le k$. Let $M_{k',\ell}$ be
the lowest position of $S'$ in column $\ell$; clearly, $k'\ge k$.
We must have $M_{k',\ell-1} = 1$ (as the only way to move from a column to
the next is by a right move). If $M_{i,\ell}=1$ then $M_{i,\ell}$
is added to $S$ by making a right move, and $i\le k\le k'$ as
required. Otherwise, $S$ is extended by a sequence of skipping
upward moves in column $\ell-1$ followed by a right move between
$M_{i',\ell-1}$ and $M_{i',\ell}$ where $i'$ is the smallest index
$\ge i$ for which both $M_{i',\ell-1}$ and $M_{i',\ell}$ are one.
But since $i\le k'$ and $M_{k',\ell-1}$ and $M_{k',\ell}$ are both
$1$, we get that $i' \le k'$, as required.
\end{proof}


\paragraph{Running time.}
The entries of $M$ that the decision procedure tests form a row-
and column-monotone path, with an additional entry to the right for
each upward turn of the path. (This also takes into account the
$0$-entries of $M$ that are inspected during a skipping upward move.)
Therefore it runs in $O(m+n)$ time.

\section{One-sided DFDS optimization via approximate distance counting and selection}
\label{sec:tec}

We now show how to use the decision procedure of Figure~\ref{alg:semi-sparse} to solve the optimization problem of the one-sided discrete Fr\'echet distance with shortcuts. This is based on the algorithms provided in Lemma \ref{lem:finding_interval} and Lemma
\ref{lem:searching_in_interval} given below. We believe that the algorithm of Lemma~\ref{lem:finding_interval} is of independent interest, and give another application of it to a different distance-related problem in Corollary~\ref{cor:aprox_selection} below.

First note that if we increase $\delta$
continuously, the set of $1$-entries of $M$ can only grow, and
this can only happen when $\delta$ is a distance between a point of $A$ and a
point of $B$. Performing a binary search over the $O(mn)$ pairwise distances of pairs in
$A\times B$ can be done using the distance selection
algorithm of~\cite{KS97}. This will be the method of choice for the two-sided DFDS problem, treated in Section~\ref{sec:DFDS2}. Here however, this procedure, which takes 
$O(m^{2/3}n^{2/3}\log^3(m+n))$ time is rather excessive when compared
to the linear cost of the decision procedure. While solving the
optimization problem in close to linear time is still a challenging
open problem, we manage to improve the running time considerably, to
$O((m+n)^{6/5+\eps})$, for any $\eps>0$. 

We first present the two main subproblems that the algorithm uses as independent building blocks, in the following two lemmas.

\begin{lemma}
\label{lem:finding_interval} Given a set $A$ of $m$ points and a set
$B$ of $n$ points in the plane, an interval
$(\alpha,\beta]\subset\reals$, and parameters $0 < L \leq mn$ and
$\eps>0$, we can determine, with high probability, whether
$(\alpha,\beta]$ contains at most $L$ distances between pairs in
$A\times B$. If $(\alpha,\beta]$ contains more than $L$ such
distances, we return a sample of $O(\log(m+n))$ pairs, so that, with
high probability, at least one of these pairs determines an
approximate median (in the middle three quarters) of the pairwise
distances that lie in $(\alpha,\beta]$. Our algorithm  runs in
 $O((m+n)^{4/3+\eps}/L^{1/3} +m+n)$ time and uses
$O((m+n)^{4/3+\eps}/L^{1/3} +m+n)$ space.
\end{lemma}

\begin{proof}
We partially construct a batched range counting data structure
for representing (some of) the pairs $(p,q)\in A \times B$ whose distance lies
in $(\alpha,\beta]$, as the edge-disjoint union of complete bipartite
graphs. If we build the complete data structure, it will require
$O((m+n)^{4/3+\eps})$ time and $O((m+n)^{4/3+\eps})$ storage (similar
to the parameters of the structure of~\cite{KS97} used in Section~\ref{sec:DFDS2}).
Since this is too expensive, we run the construction
until it reaches a level where the size of each subproblem is at most
$L$ (details will follow shortly), and then stop. The pairwise distances of $A\times B$
that fall in $(\alpha,\beta]$ are now of two types, those recorded in the
complete bipartite graphs that we have constructed, and those where the
two points belong to the same remaining ``leaf'' subproblem. We estimate the
number of distances of the latter type using an appropriate random sample of
points. As we show later, this also allows us to return a sample that contains
an approximate median of the pairwise distances in $(\alpha,\beta]$, with high
probability, if the number of these distances is indeed larger than $L$.

In more detail, we proceed as follows. Let $C$ denote the collection
of the circles bounding the  $(\alpha,\beta)$-annuli that are
centered at the points of $A$. We choose a sufficiently large
constant parameter $1 \leq r \leq m$, and construct a
$(1/r)$-cutting for $C$. That is, for a suitable constant $c$, we
partition the plane into $k\leq cr^2$ cells
$\Delta_1,\ldots,\Delta_k$, each of constant description complexity,
so that each $\Delta_i$ is crossed by at most $m/r$ boundaries of
the annuli, and each $\Delta_i$ contains at most $n/r^2$ points of
$B$. This can be done in $O((m+n)r)$ deterministic time,  as
in~\cite{Cha93,CF90,Mat91}.\footnote{The construction
in~\cite{Cha93,CF90,Mat91} shows that each $\Delta_i$ is crossed by
at most $m/r$ circles in $C$. To ensure that each
$\Delta_i$ contains at most $n/r^2$ points of $B$, we duplicate each
$\Delta_i$ that contains more than $n/r^2$ points as many times as
needed, and assign to each copy a subset of at most $n/r^2$ of the
points (these sets are pairwise disjoint and cover all the points in the cell).
Then each cell of the resulting subdivision contains at most
$n/r^2$ points, and the size of the cutting is still $O(r^2)$.} We
then dualize the roles of $A$ and $B$, in each cell $\Delta_i$
separately, where the set $B_{\Delta_i}$ of the at most $n/r^2$
points of $B$ in $\Delta_i$ becomes a set of $(\alpha,\beta)$-annuli
centered at these points, and the set $A_{\Delta_i}$ of the at most
$m/r$ points of $A$ whose annuli boundaries cross $\Delta_i$ is now
regarded as a set of points. We now construct, for each $\Delta_i$,
a $(1/r)$-cutting in this dual setting. We obtain a total of at most
$c^2r^4$ subproblems, each involving at most $m/r^3$ points of $A$
and at most $n/r^3$ points of $B$.

In both the primal and dual stages, we output a collection
of complete bipartite graphs, one for each (primal or dual) cell $\Delta_i$.
The sets of vertices of the graph associated with $\Delta_i$ are the
set of points whose annuli fully contain $\Delta_i$ and the set of
points contained in $\Delta_i$ (one of these sets is a subset of $A$
and the other is a subset of $B$). The total vertex-size over all these
graphs is at most $c'(r)(m+n)$, for some constant $c'(r)$ depending on $r$.

We now process each of the $O(r^4)$ subproblems recursively, using the
same parameter $r$, and keep doing so until we get subproblems of size
at most $L$ (in terms of the number of $A$-points plus the number of $B$-points). If this happens at
level $j$ of the recursion, we have (roughly) $(m+n)/r^{3j} = L$, or
$r^j = ((m+n)/L)^{1/3}$. The number of subproblems is at most
$c^{2j}r^{4j} = c^{2j} ((m+n)/L)^{4/3}$. If we choose $r$ sufficiently large,
we can bound $c^{2j}$ by ${(r^j)}^\eps$, where $\eps$ is the positive parameter
prespecified in the lemma.
The total (vertex) size of the graphs output so far is dominated by the
size of the graphs output at the last level, which is at most
$$
c^{2j}c'(r) r^{4j} \cdot (m+n)/r^{3j} \leq c'(r) (m+n)r^{j(1+\eps)} \leq
c'(r) (m+n)^{4/3+\eps}/L^{1/3} .
$$
With some care (again, see~\cite{Cha93,CF90,Mat91}), this also
bounds the cost of constructing the structure.

We count (within the same time bound) the number $N_1$ of edges in the
graphs produced by the algorithm.  If $N_1$ exceeds $L/2$, we generate a
random sample $R_1$ of $c_1\log (m+n)$ pairs of points (i.e., edges) from
these graphs, for some sufficiently large constant $c_1>0$. We omit the routine
details of the sampling mechanism, but remark that it ensures that each of the
sampled distances is a random element of the (uniform distribution on the)
set of all distances recorded by the graphs.  By construction, all sampled
distances lie in $(\alpha,\beta]$. Moreover, with high probability, the sample
contains an approximate median (in the \emph{middle half}) of these distances;
the routine justification of this claim is provided below.

Each subproblem at the bottom of the recursion may contain additional distances
that lie in $(\alpha,\beta]$; these are distances between centers of annuli
whose boundaries cross the cell of the subproblem and points in the cell that
lie inside these annuli.  Denote by $N_2$ the overall number of these distances
at the bottom subproblems ($N_2$ is not known to us). Note that the total number
of pairs in the subproblems is
$$M:= O(((m+n)/L)^{4/3+\eps}\cdot L^2) = O((m+n)^{4/3+\eps}L^{2/3}).$$
Our next step is to determine (approximately) how many of these distances lie inside
$(\alpha,\beta]$; that is, our goal is to estimate $N_2$.
To this end, we generate a random sample $R_2$ of $c_2(M/L)\log (m+n)$ pairs from these subproblems, for some sufficiently large constant $c_2>0$, and check how
many of them lie in $(\alpha,\beta]$. (Again, the sampling mechanism is straightforward, and we omit its details.) Let $R_2'$ denote the subset of $R_2$ of those pairs whose distances lie in $(\alpha,\beta]$. It can be shown, similar to the
analysis of Har-Peled and Sharir \cite{HS11} (which in turn is based on
the work of Li et al.~\cite{LLS01}) that, with high probability, $N_2$ is at most $L/2$ if and only if
the number of distances in $R_2'$ is $O(\log (m+n))$, for an appropriate constant of proportionality.
(Sharir and Shaul~\cite{ShSh}, who also use this tool, call such samples \emph{shallow $\eps$-nets}.)



If $N_1\leq L/2$ and we have determined that $N_2 \leq L/2$ too, then $N_1+N_2$ is at most $L$, and we terminate the algorithm (for the task considered in the lemma), since we have determined that the number of distances of $A\times B$ that lie in $(\alpha,\beta]$ is at most $L$.
Otherwise, with high probability, $R_1 \cup R_2$ contains an approximate median (in the middle three quarters) of the pairwise distances of $A\times B$ in $(\alpha,\beta]$.
In more detail, in the case under consideration we either have $N_1 >L/2$ or $N_2>L/2$ (or both). In the former case, the probability that $R_1$ does not contain a pair of distances in the middle half of the distances recorded in the complete bipartite graphs is $(1/2)^{c_1\log (m+n)} = 1/(m+n)^{c_1}$.
If $N_2>L/2$, then the probability that $R_2$ does not contain a pair at distance in the middle half  of the corresponding $N_2$ distances is
$$
\left(1-\dfrac{N_2}{2M}\right)^{c_2(M/L)\log(m+n)} < e^{-\frac{1}{2}c_2(N_2/L)\log(m+n)}<e^{-\frac{1}{4}c_2\log(m+n)} <
\dfrac{1}{(m+n)^{c_2/4}}.
$$
Assume for the moment that both $N_1$ and $N_2$ are greater than $L/2$. Then, with high probability, $R_1$ contains a pair $(a_1',b_1')$ whose distance,
$d_1$, lies in the middle half of the distances recorded in the graphs. Similarly, $R_2'$ contains a pair $(a_2',b_2')$ whose distance, $d_2$, lies in the
middle half of the distances in $(\alpha,\beta]$ that are generated by the leaf subproblems. An easy calculation shows that either $d_1$ or $d_2$ must lie in the
middle three quarters of the overall set of distances in $(\alpha,\beta]$. Similar reasoning applies when either only $N_1$ or only $N_2$ is greater than $L/2$.
We thus return $R_1\cup R_2'$ as the output of the algorithm.

The cost of the algorithm is composed from the following sub-costs:

\noindent{(i)}
We pay $O((m+n)^{4/3+\eps}/L^{1/3})$ for the partial construction of the data structure.

\noindent{(ii)}
We then sample and test
\begin{align*}
& O((M/L)\log (m+n)) = O\left(\left((m+n)^{4/3+\eps}L^{2/3}/L\right)\log (m+n)\right) =  & O\left((m+n)^{4/3+\eps}/L^{1/3}\right)
\end{align*}
pairs in
the bottom subproblems, for another, but still arbitrarily small $\eps>0$, at the same asymptotic cost.

\end{proof}

The way it is described, the algorithm does not verify that the
samples that it returns satisfy the desired properties, nor does it
verify that the number of distances in $(\alpha,\beta]$ is indeed at
most $L$, when it makes this assertion. As such, the running time is
deterministic, and the algorithm succeeds with high probability
(which can be calibrated by the choice of the constants $c_1, c_2$).
See below for another comment regarding this issue.


We use the procedure provided by
Lemma~\ref{lem:finding_interval} to find an interval $(\alpha,
\beta]$ that contains at most $L$ distances between pairs of
$A\times B$, including $\delta_F^-(A,B)$. We find this interval
using binary search, starting with $(\alpha,\beta]=(0,\infty)$, say.
In each step of the search, we run the algorithm of
Lemma~\ref{lem:finding_interval}. If it determines that the number
of critical distances in $(\alpha,\beta]$ is at most $L$ we stop. (The concrete choice of $L$ that we will use is given later.)
Otherwise, the algorithm returns a random sample $R$ that contains,
with high probability, an approximate median (in the middle three
quarters) of the distances in $(\alpha,\beta]$. We then find two consecutive distances $\alpha',\beta'$ in $R$ such that $\delta_F^-(A,B)\in (\alpha',\beta']$,
using the decision procedure (see Figure~\ref{alg:semi-sparse}). $(\alpha',\beta']$ is
a subinterval of $(\alpha,\beta]$ that contains, with high
probability, at most $7/8$ of the distances in $(\alpha,\beta]$. We
then proceed to the next step of the binary search, applying again
the algorithm of Lemma~\ref{lem:finding_interval} to the new
interval $(\alpha',\beta']$. The resulting algorithm runs in
$O((m+n)^{4/3+\eps}/L^{1/3}+(m+n)\log(m+n))$ time, for any
$\eps>0$.



Once we have narrowed down the interval $(\alpha, \beta]$, so
that it now contains at most $L$ distances between pairs of $A\times B$,
including $\delta_F^-(A,B)$, we can find $\delta_F^-(A,B)$ by
simulating the execution of the decision procedure at the unknown
$\delta_F^-(A,B)$. A simple way of doing this is as follows. To determine whether  $M_{i,j}=1$  at
$\delta_F^-(A,B)$, we compute the critical distance
$r' = \|a_i-b_j\|$ at which $M_{i,j}$ becomes $1$. If $r' \le \alpha$
then $M_{i,j}=0$, and if $r' \ge \beta$ then $M_{i,j}=1$.
Otherwise, $\alpha < r' < \beta$ is one of the at most $L$ distances
in $(\alpha, \beta]$. In this case we run the decision procedure at
$r'$ to determine $M_{i,j}$. Since there are at most $L$ distances
in $(\alpha, \beta]$, the total running time is $O(L(m+n))$. By
picking $L= (m+n)^{1/4+\eps}$ for another, but still arbitrarily
small $\eps > 0$, we balance
the bounds of $O((m+n)^{4/3+\eps}/L^{1/3}+(m+n)\log(m+n))$ and
$O(L(m+n))$, and obtain the bound of $O((m+n)^{5/4+\eps})$, for any $\eps >0$,
on the overall running time.

Although this significantly improves the naive implementation
mentioned earlier, it suffers from the weakness that it has to run
the decision procedure separately for each distance in
$(\alpha, \beta]$ that we encounter during the simulation. Lemma~\ref{lem:searching_in_interval}
shows how to accumulate several unknown distances and resolve them all
using a binary search that is guided by the decision procedure.
This allows us to find $\delta_F^-(A,B)$ within the interval
$(\alpha, \beta]$ more efficiently.


\begin{lemma}
\label{lem:searching_in_interval}
Given a set $A$ of $m$ points and a set $B$ of $n$ points in the plane, and
an interval $(\alpha,\beta]\subset\reals$ that contains at most $L$ distances
between pairs in $A\times B$, including $\delta_F^-(A,B)$, we can find
$\delta_F^-(A,B)$ in $O((m+n)L^{1/2}\log(m+n))$ (deterministic) time using $O(m+n)$ space.
\end{lemma}

\begin{proof}
We simulate the decision procedure (of Figure~\ref{alg:semi-sparse}) at the unknown value $\delta^- = \delta_F^-(A,B)$. During the simulation, when
attempting to retrieve specific entries $M_{i,j}$ of $M$, we encounter comparisons between $\delta^-$ and concrete distances between pairs of points in
$A\times B$. When we need to compare $\delta^-$ with such a distance $r'$, we first check whether $r'$ is in $(\alpha,\beta]$. If not, we know the result of the
comparison (if $r' \leq\alpha$ then $r'<\delta^-$, and if $r'> \beta$ then $r'> \delta^-$). If $\alpha <r'\leq\beta$, we bifurcate, continuing along two
possible paths, one assuming that $r'\leq\delta^-$ and one assuming that $r' > \delta^-$. However, we proceed along
each of these paths for only $s$ steps, for another parameter $s$ that will be specified shortly. (More precisely, we proceed until we
have examined $s$ known entries of $M$ (i.e., entries lying outside $(\alpha, \beta]$), including $0$-entries that we encounter
as we climb upwards in a column.)


If, before examining $s$ entries, we encounter another unknown entry,
we bifurcate again, and keep doing so, until we have examined a total of
$m+n$ entries of $M$, in which case we terminate the current ``phase''.
(It is conceivable that some entries of $M$ are examined more than once
in this procedure, but when such a multiply-visited entry is unknown,
we bifurcate there only once.) The resulting object is a binary tree $T$,
with some number, $x$, of outdegree-$2$ nodes (at which we have bifurcated),\footnote{%
 Technically, when we are at some known entry
 $M_{i,j}$, check its right neighbor $M_{i,j+1}$, and find that it is (known
 to be) 0, we continue the tracing upwards in column $j$. This 2-way exploration
 is not considered a bifurcation in the present analysis.}
so that the maximum stretch of consecutive outdegree-$1$ nodes is $s$,
and so that the total number of nodes in the tree is at most $m+n$.

We now sort the set $X$ of the $x=O(m+n)$ critical values at which
we have bifurcated, in $O((m+n) \log (m+n))$ time. We then run a binary search over $X$, using the decision procedure (of Figure~\ref{alg:semi-sparse}) to guide the search.
This step also takes $O((m+n)\log (m+n))$ time. This determines all the $x$ unknown
values that we have encountered, and allows us to choose the lowest
path in $T$ that is still a semi-sparse staircase, as the next portion of the overall lowest semi-sparse path $S$ in $M$
(at the optimal value $\delta^-$). This also allows us to shrink the interval that is known to contain $\delta^-$ to be bounded by two consecutive critical
values of $\{\alpha, \beta\} \cup X$. What we have gained, in a ``successful''
phase, is at least $s$ extra steps of the desired semi-sparse path $S$. Assuming this to be
the case, and since the total length of $S$ is $O(m+n)$, we need
at most $O((m+n)/s)$ successful phases of this kind, whose total cost is thus $O(((m+n)^2/s)\log (m+n))$.



This is only one side of the story, though, because there might be phases where
we do not manage to gain $s$ steps, because we run into ``too many''
bifurcations. If a phase generates $x$ bifurcations, then, continuing
the search in $M$ beyond them, we encounter at most $xs$ entries of $M$.
The reason for not having a ``tail'' of $s$ entries beyond any bifurcation
is that we have exceeded the number of steps per phase, namely $m+n$.
We thus have $m+n\le xs$ or $x\ge (m+n)/s$. In other words, the number of
such ``unsuccessful'' phases is $O(Ls/(m+n))$, and each such phase takes $O((m+n)\log (m+n))$
time, as before, for a total of $O(Ls\log(m+n))$ time. At the end of the simulation, we have two consecutive critical values $\alpha, \beta$ of distances between pairs of $A\times B$, where $\alpha<\delta^- \leq \beta$, so we conclude that $\delta_F^-(A,B) = \delta^- =\beta$.



Overall, the cost is
$$
O\left( \dfrac{(m+n)^2\log (m+n)}{s} + Ls\log(m+n) \right) ,
$$
and we make the
overall cost of this stage $O\left((m+n)L^{1/2}\log(m+n)\right)$, by choosing $s=(m+n)/L^{1/2}$ to balance the terms.

Note that after each phase  of the algorithm, we can free the memory
used to process the phase and only remember $\alpha,\beta$ and the
path in $M$ (a prefix of the desired $S$) that we have traversed so
far. Since each phase processes $O(m+n)$ entries of $M$, the space
needed by this algorithm is $O(m+n)$.
\end{proof}


\medskip
To balance the two terms in Lemma~\ref{lem:finding_interval} and
Lemma~\ref{lem:searching_in_interval}, we choose $L = (m + n)^{2/5+\eps}$,
for another, but still arbitrarily small $\eps > 0$. This gives the
following main result of this section.

\begin{theorem}
\label{thm:one_sided}
Given a set $A$ of $m$ points and a set $B$ of $n$ points in the plane,
and a parameter $\eps>0$, we can compute the one-sided discrete Fr\'echet
distance $\delta_F^-(A,B)$ with shortcuts in randomized expected time
$O((m+n)^{6/5+\eps})$ using $O((m+n)^{6/5+\eps})$ space.
\end{theorem}

\begin{proof}
All the details of the proof have already been given, except for the precise statement concerning the running time. As noted earlier, the algorithm of Lemma~\ref{lem:finding_interval} does not verify explicitly that the sample that it generates does contain an
approximate median, nor does it verify that the number of distances in $(\alpha,\beta]$ is at most $L$ when it so asserts.


We can either let things stay as they are, knowing that the algorithm will succeed with
overall high probability. Alternatively, as asserted in the theorem, we can realize that
something went wrong in one of two situations: Either we apply the algorithm of
Lemma~\ref{lem:finding_interval} too many times, or we encounter a total of more than
$L$ bifurcations during the execution of the algorithm of Lemma~\ref{lem:searching_in_interval}.
In these cases we scrap the whole execution and start afresh from scratch.
The expected number of rounds of this kind is $O(1)$, and the theorem follows.
\end{proof}


\paragraph{Remark.}
In principle, our algorithm for the one-sided Fr\'echet distance with shortcuts can be generalized to higher dimensions. The only part that limits our approach to $\mathbb{R}^2$ is the algorithm of Lemma~\ref{lem:finding_interval}. However, this part can be replaced by a random sampling approach that is similar to the one that we use in Lemma~\ref{lem:semi_cont_finding_interval} for the semi-continuous Fr\'echet distance with shortcuts. This will increase the running time of the algorithm, but it will stay strictly subquadratic.

We believe that Lemma~\ref{lem:finding_interval} is of independent interest,
and that it may find other applications in distance-related optimization
problems. Here is one such example.

\begin{corollary}
\label{cor:aprox_selection}
Given a set $A$ of $m$ points and a set $B$ of $n$ points in the plane,
and parameters $0<k<mn$, $0<L<k$, and $\eps>0$, we can find a pair
$(a,b) \in A\times B$ such that, with high probability, $\|a-b\|$ is the
$\kappa$th smallest distance between a point of $A$ and a point of $B$,
for some rank $\kappa$ satisfying $k-L<\kappa<k+L$, in
$O((m+n)^{4/3+\eps}/L^{1/3}+m+n)$ time, using
$O((m+n)^{4/3+\eps}/L^{1/3}+m+n)$ space.
\end{corollary}

\begin{proof}
Consider the following decision problem (already discussed earlier).
Given a set $A$ of $m$ points, a set $B$ of $n$ points, a parameter
$\delta>0$ and a parameter $0<k<mn$, determine whether the number,
$N$, of pairs in $A\times B$ at distance at most $\delta$ is at most
$k$. To solve this decision problem, we use the algorithm of
Lemma~\ref{lem:finding_interval} with $k$ as its parameter $L$, but
we replace the annuli centered at the points of $A$ and $B$ by
respective disks of radius $\delta$ centered at the same points.
Since a point $a\in A$ is at distance at most $\delta$ from a point
$b\in B$ if and only if $a$ is in the disk of radius $\delta$
centered at $b$, and vice versa, the algorithm allows us to
determine, with high probability, whether $N$ is at most $k$.
The cost of this step is $O((m+n)^{4/3+\eps}/k^{1/3} +m+n)$, and
it is subsumed by the cost of the further steps.

Let $\delta^k(A,B)$ denote the $k$th smallest distance between a
point of $A$ and a point of $B$. We now use again the algorithm of
Lemma~\ref{lem:finding_interval}, together with the above decision
procedure, to find an interval $(\alpha, \beta]$ that contains at
most $L$ pairwise distances from $A\times B$, including
$\delta^k(A,B)$. To this end, we repeatedly shrink $(\alpha, \beta]$
using a binary search, starting with $(\alpha,\beta]=(0,\infty)$,
say. In each step of the search, we call the algorithm of
Lemma~\ref{lem:finding_interval} (this time, in its original
setup, with $L$ as the parameter). If it determines that the
number of critical distances in $(\alpha,\beta]$ is at most $L$, we
output $\alpha$ (together with its generating pair) as an
approximation for $\delta^k(A,B)$, in the sense asserted in the
lemma ($\beta$ would do equally well). Otherwise, we have a random
sample $R$ that contains, with high probability, an approximate
median (in the middle three quarters) of the pairwise
distances in $(\alpha,\beta]$. We locate a
consecutive pair $x,y$ of distances in $R$, using the decision procedure, such that the interval
$(x,y]$ contains $\delta^k(A,B)$. Since $R$ contains an approximate
median, the number of distances in $(x,y]$ is, with high probability,
at most ${7/8}$ of the number of distances in $(\alpha,\beta]$. We
then proceed with the next step of the  search. The overall
resulting algorithm runs in $O((m+n)^{4/3+\eps}/L^{1/3}+m+n)$ time,
and it uses $O((m+n)^{4/3+\eps}/L^{1/3} +m+n)$ space.
\end{proof}

\paragraph{Remark.}
This should be compared with the near-linear algorithms in~\cite{BS02,HR13}
that approximate the \emph{value} of the $k$th smallest distance in $A\times B$
(rather than its rank as provided in Corollary~\ref{cor:aprox_selection}).
It would be interesting to understand better the relationship between these algorithms and ours.



\section{The two-sided DFDS}
\label{sec:DFDS2}

We first consider the corresponding decision problem.
That is, given $\delta>0$, we wish to decide whether
$\delta_F^{+}(A,B)\le\delta$.

Consider the matrix $M$ as defined in Section~\ref{sec:DFDS1}.
In the two-sided version of DFDS, given a reachable position
$(a_{i},b_{j})$ of the frogs, the $A$-frog can make a \emph{skipping
upward move}, as in the one-sided variant, to any point $a_{k},k>i$,
for which $M_{k,j}=1$. Alternatively, the $B$-frog can jump to any
point $b_{l},l>j$, for which $M_{i,l}=1$; this is a \emph{skipping
right move} in $M$ from $M_{i,j}=1$ to $M_{i,l}=1$, defined
analogously. Determining whether $\delta_F^{+}(A,B)\le\delta$
corresponds to deciding whether there exists a \emph{sparse
staircase} of ones in $M$ that starts at $M_{1,1}$, ends at
$M_{m,n}$, and consists of an interweaving sequence of skipping
upward moves and skipping right moves (see
Figure~\ref{fig:staircase}(c)).

Katz and Sharir~\cite{KS97} showed that the set
$S=\{(a_{i},b_{j})\mid\|a_{i}-b_{j}\|\le\delta\}=\{(a_{i},b_{j})\mid
M_{i,j}=1\}$ can be computed, in $O((m^{2/3}n^{2/3}+m+n)\log n)$
time and space, as the union of the edge sets of a collection
$\Gamma=\{A_{t}\times B_{t} \mid A_{t}\subseteq A, \; B_{t}\subseteq
B\}$ of edge-disjoint complete bipartite graphs. The number of
graphs in $\Gamma$ is $O(m^{2/3}n^{2/3}+m+n)$, and the overall sizes
of their vertex sets are
\[
\sum_{t}|A_{t}|,\sum_{t}|B_{t}|=O((m^{2/3}n^{2/3}+m+n)\log n).
\]
%% Each pair in $S$ thus appears in exactly one of these graphs.
We store each graph
$A_{t}\times B_{t}\in\Gamma$ as a pair of sorted linked lists $L_{A_{t}}$
and $L_{B_{t}}$ over the points of $A_{t}$ and of $B_{t}$, respectively.
For each graph $A_{t}\times B_{t}\in\Gamma$, there is $1$ in each entry $M_{i,j}$ such that $(a_{i},b_{j})\in A_{t}\times B_{t}$.
That is, $A_t \times B_t$ corresponds to a submatrix
$M^{(t)}$ of ones in $M$ (whose rows and columns are not necessarily
consecutive). See Figure~\ref{fig:submatrices}(a).

Note that if $(a_{i},b_{j})\in A_{t}\times B_{t}$ is a reachable
position of the frogs, then every pair in the set $\{(a_{k},b_{l})\in A_{t}\times B_{t}\mid k\ge i,l\ge j\}$
is also a reachable position. (In other words, the positions
in the upper-right submatrix of $M^{(t)}$ whose lower-left entry
is $M_{i,j}$ are all reachable; see Figure~\ref{fig:submatrices}(b)).

\begin{figure}[htb]
\centering \includegraphics[scale=0.6]{submatrices}
\centering \caption{\small(a) A possible representation of the matrix $M$ as a collection of submatrices of ones, corresponding to the complete bipartite graphs $\{a_1,a_2\}\times\{b_1, b_2\},
 \{a_1, a_3, a_5\}\times \{b_4, b_6\},
 \{a_1,a_3\}\times\{b_7, b_{11}\},
 \{a_2, a_3,a_5\}\times\{b_5, b_8, b_9\},
 \{a_4, a_7, a_8\}\times\{b_3, b_4\},
\{a_4, a_7\}\times\{b_8, b_{10}\},
\{a_6\}\times \{b_9, b_{11}\},
\{a_8\}\times \{b_9,b_{12}\}$. (b) Another matrix $M$, similarly decomposed, where the reachable positions
are marked with an x.}
\label{fig:submatrices}
\end{figure}

We say that a graph $A_{t}\times B_{t}\in\Gamma$ \emph{intersects}
a row $i$ (resp., a column $j$) in $M$ if $a_{i}\in A_{t}$ (resp., $b_j\in B_{t}$). We denote the subset of graphs of $\Gamma$ that
intersect the $i$th row of $M$
by $\Gamma_{i}^{r}$ and those that intersect the $j$th column by $\Gamma_j^c$. The sets $\Gamma_i^r$ are easily constructed from the lists $L_{A_t}$ of the graphs in $\Gamma$, and are maintained as linked lists.
Similarly, the sets $\Gamma_j^c$ are constructed from the lists $L_{B_t}$, and are maintained  as doubly-linked lists, so as to facilitate deletions of elements from them. We have $\sum_{i}|\Gamma_{i}^{r}|=\sum_{t}|A_{t}|=O((m^{2/3}n^{2/3}+m+n)\log n)$
 and
$\sum_{j}|\Gamma_{j}^{c}|=\sum_{t}|B_{t}|=O((m^{2/3}n^{2/3}+m+n)\log n).$

%\matya{I modified the following two paras which are delicate, pls check.}
We define a 1-entry $(a_k, b_j)$
to be {\em reachable from below row $i$}, if $k \geq i$ and there exists an entry
$(a_\ell, b_j)$, $\ell < i$, which is reachable.
We process the rows of $M$ in increasing order
and for each graph $A_{t}\times B_{t}\in\Gamma$  maintain a
reachability variable $v_t$, which is initially set to $\infty$.
We maintain the invariant that when we
start processing row $i$, 
if $A_t\times B_t$ intersects at least one row that is not below the $i$th row, then
$v_t$ stores the smallest index $j$ 
for which there exists an entry $(a_k,b_j) \in A_{t}\times B_{t}$
that is reachable from below row $i$.


Before we start processing the rows of $M$, we verify that
$M_{1,1}=1$ and $M_{m,n} = 1$, and abort the computation if this
is not the case, determining that $\delta_F^{+}(A,B)>\delta$.

Assuming that $M_{1,1}=1$, each position in $P_1=\{(a_{1},b_{l})
\mid M_{1,l}=1\}$ is a reachable position. It follows that for each
graph $A_t\times B_t \in \Gamma$, $v_t$ should be set to
$\min\{l\mid A_t\times B_t\in \Gamma_l^c \text{ and } (a_1, b_l)\in
P_1\}$. Note that graphs $A_t\times B_t$ in this set are not necessarily in $\Gamma_1^r$.
%\matya{I changed $\Gamma_i^r$ to $\Gamma_1^r$ in the previous sentence.}
We update the $v_t$'s using this rule, as follows. We
first compute $P_1$, the set of pairs, each consisting of $a_1$ and
an element of the union of the lists $L_{B_t}$, for $A_t\times
B_t\in \Gamma_1^r$. Then, for each $(a_1,b_l) \in P_1$, we set, for
each graph $A_u\times B_u \in \Gamma_l^c$, $v_u \leftarrow
\min\{v_u,l\}$.
%Clearly, this step updates all graphs in
%$\Gamma_l^c$.

In principle, this step should now be repeated for each row $i$.
That is, we should compute $y_i=\min\{v_t\mid A_t\times B_t\in
\Gamma_i^r\}$; this is the index of the leftmost entry of row $i$
that is reachable from below row $i$. Next, we should compute
$P_i=\{(a_i,b_l)\mid M_{i,l}=1 \text{ and } l\geq y_i\}$ as the
union of those pairs that consist of $a_i$ and an element of
$$
%\label{eqn:v_t}
\{ b_j \mid b_j \in L_{B_t} \;\mbox{for}\; A_t\times B_t\in
\Gamma_i^r \;\mbox{and}\; j \ge y_i \}.$$

The set $P_i$ is the set of reachable positions in row $i$.
Then we should set for each $(a_1,b_l) \in P_i$ and for each graph
$A_u\times B_u \in \Gamma_l^c$, $v_u \leftarrow \min\{v_u,l\}$.
This however is too expensive, because it may make us construct
explicitly all the $1$-entries of $M$.

To reduce the cost of this step, we note that, for any graph
$A_t\times B_t$, as soon as $v_t$ is set to some column $l$ at some
point during processing, we can remove $b_l$ from $L_{B_t}$ because
its presence in this list has no effect on further updates of the
$v_t$'s. Hence, at each step in which we examine a graph $A_t\times
B_t \in \Gamma_l^c$, for some column $l$, we remove $b_l$ from
$L_{B_t}$. This removes $b_l$ from any further consideration in rows
with index greater than $i$ and, in particular, $\Gamma_l^c$ will
not be accessed anymore.  This is done also when processing the
first row.

Specifically, we process the rows in increasing order and when we
process row $i$, we first compute $y_i=\min\{v_t\mid A_{t}\times
B_{t}\in\Gamma_{i}^{r}\}$, in a straightforward manner. (If $i=1$, then we simply set $y_1=1$.)
%\matya{I added the last sentence in parentheses.}
Then we
construct a set $P_i' \subseteq P_i$ of the ``relevant'' (i.e., reachable)
$1$-entries in the $i$-th row as follows. For each graph  $A_t
\times B_t\in \Gamma_i^r$ we traverse (the current) $L_{B_t}$
\emph{backwards}, and for each $b_j \in L_{B_t}$ such that $j \ge y_i$
we add $(a_i,b_j)$ to $P_i'$. Then, for each $(a_i,b_l)\in P_i'$,
we go over all graphs $A_u\times B_u\in \Gamma_l^c$, and set $v_u
\leftarrow\min\{v_u,l\}$. After doing so, we remove $b_l$ from all
the corresponding lists $L_{B_u}$.

When we process row $m$ (the last row of $M$), we set
$y_m=\min\{v_t\mid A_{t}\times B_{t} \in\Gamma_{m}^{r}\}$. If
$y_m<\infty$, we conclude that $\delta_F^{+}(A,B)\le\delta$
(recalling that we already know that $M_{m,n}=1$). Otherwise, we
conclude that $\delta_F^{+}(A,B)>\delta$.

\paragraph{Correctness.}
We need to show that $\delta_F^{+}(A,B)\le\delta$ if  and only if
$y_m <\infty$ (when we start processing row $m$).  To this end, we
establish in Lemma~\ref{lem:two_sided} that the invariant stated above
regarding $v_t$ indeed holds. Hence, if $y_m<\infty$, then the
position $(a_m,b_{y_m})$ is reachable from below row $m$,
implying that $(a_m,b_n)$ is also a reachable position and thus
$\delta_F^{+}(A,B)\le\delta$. Conversely, if
$\delta_F^{+}(A,B)\le\delta$ then $(a_m,b_n)$ is a reachable
position. So, either $(a_m,b_n)$ is reachable from below row $m$, or
there exists a position $(a_m, b_j)$, $j<n$, that is reachable from
below row $m$ (or both). In either case there exists a graph
$A_t\times B_t$ in $\Gamma_m^r$ such that $v_t\leq n$ and thus
$y_m <\infty$.
We next show
that the reachability variables $v_t$ of the graphs in $\Gamma$ are maintained
correctly.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{lemma}
\label{lem:two_sided} For each $i=1,\ldots,m$, the following
property holds. Let $A_t \times B_t$ be a graph in $\Gamma_i^r$, and
let $j$ denote the smallest index for which $(a_i,b_j) \in A_t\times
B_t$ and $(a_i,b_j)$ is reachable from below row $i$. Then, when we
start processing row $i$, we have $v_t = j$.
\end{lemma}

\begin{proof}
We prove this claim by induction on $i$.  For $i=1$, this claim holds trivially.
We assume then that $i>1$ and that the claim is true for each row $i'<i$,
and show that it also holds for row $i$.

Let $A_t\times B_t$ be a graph in $\Gamma_i^r$, and let $j$ denote the smallest
index for which there exists a position $(a_i, b_j) \in A_t\times B_t$ that is reachable from
below row $i$. We need to show that $v_t= j$ when we start processing row $i$.

Since $(a_i,b_j)$ is reachable from below row $i$, there exists a position
$(a_k,b_j)$, with $k<i$, that is reachable, and we let $k_0$ denote the smallest
index for which $(a_{k_0}, b_j)$ is reachable.  Let $A_o\times B_o$ be the graph
containing $(a_{k_0},b_j)$. We first claim that when we start processing row
$k_0$, $b_j$ was not yet deleted from $L_{B_o}$ (nor from the corresponding
list of any other graph in $\Gamma_j^c$). Assume to the contrary that $b_j$
was deleted from $L_{B_o}$ before processing row $k_0$. Then there exists a
row $z<k_0$ such that $(a_z, b_j)\in P_z'$ and we deleted $b_j$ from $L_{B_o}$
when we processed row $z$. By the last assumption, $(a_z,b_j)$ is a reachable
position. This is a contradiction to $k_0$ being the smallest index for which
$(a_{k_0}, b_j)$ is reachable. (The same argument applies for any other graph,
instead of $A_o\times B_o$.)

We next show that $v_t \leq j$. Since $(a_{k_0},b_j)\in A_o\times B_o$,
$A_o\times B_o \in \Gamma_{k_0}^r \cap \Gamma_j^c$. Since $k_0$ is the
smallest index for which $(a_{k_0}, b_j)$ is reachable, there exists an
index $j_0$, such that $j_0 <j$ and $(a_{k_0}, b_{j_0})$ is reachable from
below row $k_0$. (If $k_0=1$, we use instead the starting placement
$(a_1,b_1)$.) It follows from the induction hypothesis that
$y_{k_0}\leq j_0 <j$. Thus, when we processed row $k_0$ and we went
over $L_{B_o}$, we encountered $b_j$ (as just argued, $b_j$ was still in
that list), and we consequently updated the reachability variables $v_u$ of each
graph in $\Gamma_j^c$, including our graph $A_t\times B_t$ to be at most $j$.

(Note that if there is no position in $A_t\times B_t$ that is reachable
from below row $i$ (i.e., $j=\infty$), we trivially have $v_t \leq \infty$.)

Finally, we show that $v_t=j$. Assume to the contrary that $v_t=j_1<j$ when
we start processing row $i$. Then we have updated $v_t$ to hold $j_1$ when
we processed $b_{j_1}$ at some row $k_1 <i$. So, by the induction hypothesis,
$y_{k_1} \leq j_1$, and thus $(a_{k_1}, b_{j_1})$ is a reachable position.
Moreover, $A_t \times B_t \in \Gamma_{j_1}^c$, since $v_t$ has been updated
to hold $j_1$ when we processed $b_{j_1}$. It follows that
$(a_i, b_{j_1})\in A_t\times B_t$. Hence, $(a_i, b_{j_1})$ is reachable
from below row $i$. This is a contradiction to $j$ being the smallest
index such that $(a_i, b_j)$ is reachable from below row $i$. This
establishes the induction step and thus completes the proof of the lemma.
\end{proof}

\paragraph{Running Time.} We first analyze the initialization cost of
the data structure, and then the cost of traversal of the rows
for maintaining the variables $v_t$.

\paragraph{Initialization.}
Constructing $\Gamma$ takes $O((m^{2/3}n^{2/3}+m+n)\log(m+n))$ time.
Sorting the lists $L_{A_t}$ (resp., $L_{B_t}$) of each $A_{t}\times B_{t}\in\Gamma$ takes
$O((m^{2/3}n^{2/3}+m+n)\log^2 (m+n))$ time. Constructing the lists
$\Gamma_i^r$ (resp., $\Gamma_j^c$) for each $a_i \in A$ (resp., $b_j
\in B$) takes time linear in the sum of the sizes of the $A_t$'s and
the $B_t$'s, which is $O((m^{2/3}n^{2/3}+m+n)\log(m+n))$.

\paragraph{Traversing the rows.}
When we process row $i$ we
first compute $y_i$ by scanning $\Gamma_i^r$. This takes a total of 
$O\left(\sum_{i}|\Gamma_{i}^{r}|\right)=O((m^{2/3}n^{2/3}+m+n)\log
n)$ for all rows. Since the lists $L_{B_t}$ are sorted, the
computation of $P_i'$ is linear in the size of $P_i'$.
This is so because, once we have added a pair $(a_i,b_j)$ to $P'_i$,
we remove $b_j$ from all lists that contain it, so we will not encounter
it again when scanning other lists $L_{B_{t'}}$.  For each pair
$(a_i,b_\ell)\in P_i'$ we scan $\Gamma_\ell^c$, which must contain at
least one graph $A_t\times B_t \in \Gamma$ such that $a_i \in A_t$
(and $b_j\in B_t$).
For each element $A_t\times B_t\in \Gamma_\ell^c$ we spend constant
time updating $v_t$ and removing $b_\ell$ from $L_{B_t}$. It follows
that the total time, over all rows, of computing $P_i'$ and scanning
the lists $\Gamma_\ell^c$ is 
$O\left(\sum_{l}|\Gamma_{l}^{c}|\right)=O((m^{2/3}n^{2/3}+m+n)\log n)$.

We conclude that the total running time is
$O((m^{2/3}n^{2/3}+m+n)\log^2 (m+n))$.


\paragraph{The optimization procedure.}
We use the above decision procedure for finding the optimum
$\delta_F^+(A,B)$, as follows.  Note that if we increase $\delta$
continuously, the set of $1$-entries of $M$ can only grow, and
this can only happen at a distance between a point of $A$ and a
point of $B$. We thus perform a binary search over the $mn$
pairwise distances between the pairs of $A\times B$. In each
step of the search we need to determine the $k$th smallest
pairwise distance $r_k$ in $A\times B$, for some value of $k$.
We do so by using the distance selection algorithm of
Katz and Sharir~\cite{KS97}, which can easily be adapted to
work for this bichromatic scenario. We then run the decision
procedure on $r_k$, using its output to guide the binary search.
At the end of this search, we obtain two consecutive critical
distances $\delta_1, \delta_2$ such that
$\delta_1 < \delta_F^+(A,B) \leq \delta_2$, and we can
therefore conclude that $\delta_F^+(A,B) = \delta_2$. The
running time of the distance selection algorithm of \cite{KS97}
is $O((m^{2/3}n^{2/3}+m+n)\log^2(m+n))$, which also holds for the bipartite version that we use.
We thus obtain the following main result of this section.

\begin{theorem}
Given a set $A$ of $m$ points and a set $B$ of $n$ points in the
plane, we can compute the two-sided discrete Fr\'echet distance
with shortcuts $\delta_F^+(A,B)$, in time
$O((m^{2/3}n^{2/3}+m+n)\log^3 (m+n))$, using
$O((m^{2/3}n^{2/3}+m+n)\log (m+n))$ space.
\end{theorem}

\input{semi_continuous1.tex}

\section{Discussion}

The algorithms obtained for the discrete Fr\'echet distance with
shortcuts, run in time significantly better than those for the Fr\'echet
distance without shortcuts.  It is thus an interesting open question
whether similar improvements can be obtained for the continuous version of
the Fr\'echet distance with shortcuts, where shortcuts are made only
between vertices of the curves. This variant, that was considered by Driemel
and Har-Peled~\cite{DH12}, may be easier than the NP-Hard variant that was
considered by Driemel et al.~\cite{BDS13}. We hope that the techniques that we have developed for the semi-continuous problem will be useful for tackling this harder problem.
%\rinat{actually, I know it's easier
%because the authors of~\cite{BDS13} solved it in cubic time and sent it to ESA,
%but they don't mention it in the eurocg version. what are the rules? can I
%mention that?}

Another topic for further research is to find additional
applications of some of the ideas that appear in the optimization technique
for the one-sided variant.

\begin{thebibliography}{}

\bibitem{ABKS12} P.~K.~Agarwal, R.~Ben Avraham, H.~Kaplan and
M.~Sharir, Computing the discrete Fr\'echet distance in subquadratic
time, \textit{Proc. 24th Annu. ACM-SIAM Sympos. Discrete Algorithms}
(2013), 156--167. Also in \textit{SIAM J. Comput.}, in press, and in arxiv:1204.5333 (2012).

\bibitem{AG95} H.~Alt and M.~Godau, Computing the Fr\'echet distance
between two polygonal curves, \textit{Internat. J. Comput. Geom. Appl.}
5 (1995), 75--91.

%\bibitem{AKW04} H.~Alt, C.~Knauer and C.~Wenk, Comparison of distance
%measures for planar curves, \textit{Algorithmica} 38(1) (2004), 45--58.

%\bibitem{AHKWW06} B.~Aronov, S.~Har-Peled, C.~Knauer, Y.~Wang
%and C.~Wenk, Fr\'echet distance for curves, revisited, \textit{Proc.
%14th Annu. European Sympos. Algorithms} (2006), 52--63.

\bibitem{BFKKS13}
R.~Ben Avraham, O.~Filtser, H.~Kaplan, M.~J.~Katz and M.~Sharir,
The Discrete and Semicontinuous Fr\'echet Distance with Shortcuts via Approximate Distance Counting and Selection, \textit{Proc. 30th ACM Sympos. Comput. Geom.} (2014), to appear.  arxiv:1310.5245 (2013).

\bibitem{BJWYZ08}
S.~Bereg, M.~Jiang, W.~Wang, B.~Yang and B.~Zhu,
Simplifying 3d polygonal chains under the discrete Frechet distance,
\textit{Proc. 8th Latin American Conf. on Theoretical informatics} (2008), 630--641.

\bibitem{BS02}
S.~Bespamyatnikh and M.~Segal,
Fast algorithms for approximating distances,
\textit{Algorithmica} 33(2) (2002), 263--269.

\bibitem{BPSW05} S.~Brakatsoulas, D.~Pfoser, R.~Salas and C.~Wenk,
On map-matching vehicle tracking data, \textit{Proc. 31st Intl. Conf.
Very Large Data Bases} (2005), 853--864. 

\bibitem{BBG08} K.~Buchin, M.~Buchin and J.~Gudmundsson, Detecting
single file movement, \textit{Proc. 16th ACM SIGSPATIAL Intl. Conf.
Adv. GIS} (2008), 288--297.

\bibitem{BBGLL08} K.~Buchin, M.~Buchin, J.~Gudmundsson, M.~L\'effler
and J.~Luo, Detecting commuting patterns by clustering subtrajectories,
\textit{Internat. J. Comput. Geom. Appl.} 21(3) (2011), 253--282. 

\bibitem{BBMM12} K.~Buchin, M.~Buchin, W.~Meulemans and W.~Mulzer,
Four soviets walk the dog --- with an application to Alt's conjecture,
\textit{Proc. 25th Annu. ACM-SIAM Sympos. Discrete Algorithms} (2014), 1399--1413.

\bibitem{BBW09}
K.~Buchin, M.~Buchin and Y.~Wang,
Exact algorithms for partial curve matching via the Fr\'echet distance,
\textit{Proc. 20th Annu. ACM-SIAM Sympos. Discrete Algorithms} (2009), 645--654.

\bibitem{BDS13}
M.~Buchin, A.~Driemel and B.~Speckmann,
Computing the Fr\'echet distance with shortcuts is NP-hard,
\textit{Euro. Workshop Comput. Geom.} (2013), 43--46.

\bibitem{Cha93}
B.~Chazelle,
Cutting hyperplanes for divide-and-conquer,
\textit{Discrete Comput. Geom.} 9 (1993), 145--158.

\bibitem{CF90}
B.~Chazelle and J.~Friedman,
A deterministic view of random sampling and its use in geometry,
\textit{Combinatorica} 10 (1990), 229--249.

\bibitem{CDGNW11} D.~Chen, A.~Driemel, L.~J.~Guibas, A.~Nguyen
and C.~ Wenk, Approximate map matching with respect to the Fr\'echet
distance, \textit{Proc. 7th Workshop on Algorithm Engineering and
Experiments} (2011), 75--83.


\bibitem{DH12} A.~Driemel and S.~Har-Peled, Jaywalking your dog:
Computing the Fr\'echet distance with shortcuts, \textit{SIAM J. Comput.} 42(5) (2013), 1830--1866. 

%\bibitem{DHW10} A.~Driemel, S.~Har-Peled and C.~Wenk, Approximating
%the Fr\'echet distance for realistic curves in near linear time, \textit{Discrete Comput. Geom.} %48(1) (2012), 94--127. 

\bibitem{EM94} T.~Eiter and H.~Mannila, Computing discrete Fr\'echet
distance, Technical Report CD-TR 94/64, Christian Doppler Laboratory
for Expert Systems, TU Vienna, Austria, 1994.

\bibitem{HR13}
S.~Har-Peled and B.~Raichel,
Net and prune: a linear time algorithm for Euclidean distance problems,
\textit{Proc. 45th ACM Sympos. Theory Comput.} (2013), 605--614.

\bibitem{HS11}
S.~Har-Peled and M.~Sharir,
Relative $(p, \eps)$-approximations in geometry,
\textit{Discrete Comput. Geom.} 45(3) (2011), 462--496.

\bibitem{KS97} M.~J.~Katz and M.~Sharir, An expander-based approach
to geometric optimization, \textit{SIAM J. Comput.} 26(5) (1997),
1384--1408.

\bibitem{KKS05} M.~S.~Kim, S.~W.~Kim and M.~Shin, Optimization
of subsequence matching under time warping in time-series databases,
\textit{Proc. ACM Sympos. Applied Comput.} (2005), 581--586.

\bibitem{KHMTC98} S.~Kwong, Q.~H.~He, K.~F.~Man, K.~S.~Tang
and C.~W.~Chau, Parallel genetic-based hybrid pattern matching algorithm
for isolated word recognition, \textit{Intl. J. Pattern Recog. Art.
Intel.} 12(5) (1998), 573--594.

\bibitem{LLS01}
Y.~Li, P.~M.~Long and A.~Srinivasan,
Improved bounds on the sample complexity of learning,
\textit{J. Comput. Syst. Sci.} 62 (2001), 516--527.

\bibitem{Mat91}
J.~Matou\v{s}ek,
Cutting hyperplane arrangements,
\textit{Discrete Comput. Geom.}
6 (1991), 385--406.

\bibitem{MP99} M.~E.~Munich and P.~Perona, Continuous dynamic
time warping for translation-invariant curve alignment with applications
to signature verification, \textit{Proc. 7th Intl. Conf. Comp. Vision}
(1999), 108--115.


\bibitem{ShSh}
M.~Sharir and H.~Shaul,
Semialgebraic range reporting and emptiness searching with applications,
\textit{SIAM J. Comput.} 40(4) (2011), 1045--1074.

\bibitem{WSP06} C.~Wenk, R.~Salas and D.~Pfoser, Addressing the
need for map-matching speed: Localizing global curve-matching algorithms,
\textit{Proc. 18th Intl. Conf. Scientific and Statistical Database
Management} (2006), 379--388. %\bibitem{SH76}

\bibitem{WZ13}
T.~Wylie and B.~Zhu,
Protein chain pair simplification under the discrete Frechet distance,
\textit{IEEE/ACM Trans. Comput. Biology Bioinform.} (2013), 1372--1383.

\end{thebibliography}


introduction.tex
\renewcommand\thepage{\arabic{page}}
\section{Introduction}

\label{sec:introduction}

%Let us first define the Fr\'echet distance and the discrete
%Fr\'echet distance informally.

Consider a person and a dog connected by a leash, each walking along
a curve from its starting point to its end point. Both are allowed
to control their speed but they cannot backtrack. The {\em Fr\'echet
distance} between the two curves is the minimum length of a leash
that is sufficient for traversing both curves in this manner. The
\emph{discrete fr\'echet distance} replaces the curves by two
sequences of points $A = (a_1,\ldots, a_m)$ and
$B=(b_1,\ldots,b_n)$, and replaces the person and the dog by two
frogs, the $A$-frog and the $B$-frog, initially placed at $a_{1}$
and $b_{1}$, respectively. At each move, the $A$-frog or the
$B$-frog (or both) jumps from its current point to the next. The
frogs are not allowed to backtrack. We are interested in the minimum
length of a ``leash'' that connects the frogs and allows the
$A$-frog and the $B$-frog to get to $a_m$ and $b_n$, respectively.
More formally, for a given length $\delta$ of the leash, a
jump is allowed only if the distances between the two frogs before
and after the jump are both at most $\delta$; the \emph{discrete
Fr\'echet distance} between $A$ and $B$, denoted by
$\delta_F^{*}(A,B)$, is then the smallest $\delta>0$ for which there
exists a sequence of jumps that brings the frogs to $a_{m}$ and
$b_{n}$, respectively.

The Fr\'echet distance and the discrete Fr\'echet distance are used
as similarity measures between curves and sampled curves,
respectively, in many applications. Among these are speech
recognition~\cite{KHMTC98}, signature verification~\cite{MP99},
matching of time series in databases~\cite{KKS05}, map-matching of
vehicle tracking data ~\cite{BPSW05, CDGNW11, WSP06}, and analysis
of moving objects~\cite{BBG08, BBGLL08}.

In many of these applications the curves or the sampled sequences of
points are generated by physical sensors, such as GPS. These sensors
may generate inaccurate measurements, which we refer to as {\em outliers}.
The Fr\'echet distance and the discrete Fr\'echet distance are bottleneck
(min-max) measures, and are therefore sensitive to outliers, and
may fail to capture the similarity between the curves when there are
outliers, because the large distance from an outlier to the other curve
might determine the Fr\'echet distance, making it much larger than
the distance without the outliers.

In order to handle outliers, Driemel
and Har-Peled ~\cite{DH12} introduced the (continuous) Fr\'echet
distance with shortcuts. They considered piecewise linear curves and
allowed (only) the dog to take shortcuts by walking from a vertex $v$
to any succeeding vertex $w$ along the straight segment connecting $v$
and $w$. This ``one-sided'' variant allows one to ``ignore'' subcurves of
one (noisy) curve that substantially deviate from the other (more
reliable) curve. Driemel and Har-Peled gave efficient approximation algorithms for the
Fr\'echet distance in such scenarios; these are reviewed in more
detail later on.

Driven by the same motivation of reducing sensitivity to outliers,
we define two variants of the discrete Fr\'echet distance with
shortcuts. In the one-sided variant, we allow the $A$-frog to jump to
any point that comes later in its sequence, rather than just to the
next point. The $B$ frog has to visit all the $B$ points in order, as in the standard discrete Fr\'echet distance problem. However, we add the restriction that only a single frog
is allowed to jump in each move (see below for more details).
As in the standard discrete Fr\'echet distance, for a leash of length $\delta$ such a jump is
allowed only if the distances between the two frogs before and
after the jump are both at most $\delta$. The \emph{one-sided
discrete Fr\'echet distance with shortcuts}, denoted as
$\delta_F^-(A,B)$, is the smallest $\delta>0$ for which
there exists such a sequence of jumps that brings the frogs to
$a_{m}$ and $b_{n}$, respectively. 

We also define the
{\em two-sided discrete Fr\'echet distance with shortcuts},
denoted as $\delta_F^{+}(A,B)$, to be the smallest $\delta>0$ for
which there exists a sequence of jumps, where both frogs are
allowed to skip points as long as the distances between the two frogs before and
after the jump are both at most $\delta$. Here too, we allow only one of the frogs
to jump at each move.

In the (standard) discrete Fr\'echet distance, the frogs can make
simultaneous jumps, each to its next point. Here though simultaneous jumps
make the problem degenerate as it is possible for the frogs to jump
from $a_{1}$ and $b_{1}$ straight to $a_{m}$ and $b_{n}$ (in the two-sided scenario).
The one-sided version can easily be extended to the case where simultaneous jumps are allowed, but, to keep the description simple, we describe here only the case where such simultaneous jumps are not allowed, and leave it for the reader to complete the easy modifications for handling such jumps.

\paragraph{Our results.} In this paper we give efficient algorithms for
computing the discrete Fr\'echet distance with one-sided and two-sided
shortcuts. 
The
structure of the one-sided problem allows us to decide whether the distance is
no larger than a given $\delta$, in $O(n+m)$ time, and the challenge
is to search for the optimum, using this fast decision procedure,
with a small overhead. The naive approach would be to
use the $O((m^{2/3}n^{2/3}+m+n)\log (m+n))$-time distance selection
procedure of \cite{KS97}, which would make the running time
$\Omega((m^{2/3}n^{2/3}+m+n)\log (m+n))$, much higher than the
linear cost of the decision procedure.
 
To tighten this gap, we develop an algorithm that, given an interval
$(\alpha,\beta]$ and a parameter $L$, decides, with high probability and in
$O((m+n)^{4/3+\epsilon}/L^{1/3}+m+n)$ time, whether the number of
pairs in $A\times B$ of distance in $(\alpha,\beta]$ is at most $L$.
Furthermore, if this number is larger than $L$, our algorithm provides
a sample of these pairs, of logarithmic size, that contains, with high
probability, a pair at approximate median distance (in the middle three quarters of the distances
in $(\alpha,\beta]$). We combine this algorithm with a binary search to
obtain a procedure that produces an interval that contains
the optimal distance as well as at most $L$ other distances. In
addition, we give a technique to use the decision procedure in order
to find the optimal value among these $L$ remaining distances in
$O((m + n)L^{1/2} \log(m + n))$ time. As $L$ increases, the first
stage becomes faster and the second stage becomes slower. Choosing
$L$ to balance the two gives us an algorithm for the one-sided
Fr\'echet distance with shortcuts that runs in $O((m+n)^{6/5+\eps})$
time for any $\eps>0$.

We believe that this technique is of independent interest, beyond
the scope of computing the one-sided Fr\'echet distance with shortcuts,
and that it may be applicable to other optimization problems over
pairwise distances.  We give two such additional applications.
The first application, given in Corollary~\ref{cor:aprox_selection}, is rank-based approximation of the $k$th
smallest distance. That is, given $k$ and $L \le k$, we give an
algorithm for finding a distance which is the $\kappa$-th
smallest distance, for some $k-L \le \kappa \le k+L$, that runs in
$O((m+n)^{4/3+\epsilon}/L^{1/3}+m+n)$ time.

Our second application is a semi-continuous version of the one-sided
Fr\'echet distance with shortcuts. In this problem $A$ is a sequence
of $m$ points and $f\subseteq\mathbb{R}^{2}$ is a polygonal curve of
$n$ edges. A frog has to jump over the points in $A$, connected by a
leash to a person who walks on $f$. The frog can make shortcuts and
skip points, but the person must traverse $f$ continuously. The frog and the person cannot backtrack. We want to
compute the minimum length of a leash that allows the
frog and the person to get to their final positions in such
a scenario. In Section~\ref{sec:semi_cont} we present an
algorithm that runs in $O((m+n)^{2/3}m^{2/3}n^{1/3}\log(m+n))$ expected
time for this problem. While less efficient than the fully discrete
version, it is still significantly subquadratic.

For the two-sided version we take a different approach. More specifically, we implement the decision procedure by using an implicit compact
representation of all pairs in $A\times B$ at distance at most
$\delta$ as the disjoint union of complete bipartite cliques \cite{KS97}.
This representation allows us to maintain the pairs reachable by the
frogs with a leash of length at most $\delta$ implicitly and
efficiently. The cost of the decision procedure is $O((m^{2/3}n^{2/3}+m+n)\log^2 (m+n))$, which is comparable with the cost of the distance selection procedure of~\cite{KS97}, as mentioned above. We can then run a binary search for the optimal distance, using this distance selection procedure. The resulting algorithm runs in $O((m^{2/3}n^{2/3}+m+n)\log^3
(m+n))$  time and requires $O((m^{2/3}n^{2/3}+m+n)\log (m+n))$
space. 

Interestingly, the algorithms developed for these variants of the discrete Fr\'echet distance problem are sublinear in the size of $A\times B$
and way below the slightly subquadratic bound for the discrete
Fr\'echet distance, recently obtained in \cite{ABKS12}.

In principle, the algorithm for the one-sided Fr\'echet distance with shortcuts can be generalized to work in higher dimensions. See a remark in Section~\ref{sec:tec}. 

\paragraph{Background.} The Fr\'echet distance and its variants have been
extensively studied in the past two decades.
Alt and Godau~\cite{AG95} showed that the Fr\'echet distance of two
planar polygonal curves with a total of $n$ edges can be computed,
using dynamic programming, in $O(n^{2}\log n)$ time. Eiter and
Mannila~\cite{EM94} showed that the discrete Fr\'echet distance in
the plane can be computed, also using dynamic programming, in
$O(mn)$ time. Buchin et al.~\cite{BBMM12} recently
improved the bound of Alt and Godau and showed how to compute the
Fr\'echet distance in $O(n^2 (\log n)^{1/2} (\log\log n)^{3/2})$
time on a pointer machine, and in $O(n^2 (\log\log n)^2)$ time
on a word RAM \cite{BBMM12}. Agarwal et al.~\cite{ABKS12} showed
how to compute the discrete Fr\'echet distance in
$O\left(\dfrac{mn\log\log n}{\log n}\right)$ time.

As already noted, the (one-sided) continuous Fr\'echet distance
with shortcuts was first studied by Driemel and Har-Peled~\cite{DH12}.
They considered the problem where shortcuts are allowed only between
\emph{vertices} of the noise-containing curve, in the manner outlined
above, and gave approximation algorithms for
solving two variants of this problem. In the first variant,  any
number of shortcuts is allowed, and in the second variant, the
number of allowed shortcuts is at most $k$, for some $k \in
\mathbb{N}$. Their algorithms work efficiently only
for \emph{$c$-packed} polygonal curves; these are curves that
behave ``nicely'' and are assumed to be the input in practice.
Both algorithms compute a
$(3+\varepsilon)$-approximation of the Fr\'echet distance with
shortcuts between two $c$-packed polygonal curves and both run in
near-linear time (ignoring the dependence on $\varepsilon$).
%\micha{Didnt Rinat mention an $O(n^3)$ exact algorithm? Mention it too here?}
%\rinat{The $O(n^3)$ exact algorithm are of Buchin et al and was not published.}
Buchin et al.~\cite{BDS13} consider a more general version of the
(one-sided) continuous Fr\'echet distance with shortcuts, where
shortcuts are allowed between any pair of points of the noise-containing
curve. They show that this problem is NP-Hard. They also give a 3-approximation algorithm for the decision version of this problem
that runs in $O(n^3 \log n)$ time.

In contrast with the results just reviewed, our results are somewhat surprising, as they demonstrate that both
variants of the discrete Fr\'echet distance with shortcuts are
easier to compute (exactly, with no restriction on the input)
than all previously studied variants of the Fr\'echet distance.

We also note that there have been several other works that treat outliers
in different ways. One such result is of Buchin et al.~\cite{BBW09}, who considered the partial Fr\'echet similarity problem, where one is given two curves $f$ and $g$, and a distance threshold $\delta$, and the goal is to maximize the total length of the portions of
$f$ and $g$ that are matched (using the Fr\'echet distance paradigm) with $L_p$-distance smaller than $\delta$.
They gave an algorithm that solves this problem in $O(mn(m + n) \log(mn))$ time, under the $L_1$ or $L_\infty$ norm.
The definition of the partial Fr\'echet similarity aims at situations where the extent of a prerequired similarity is known (and given by the distance thereshold $\delta$), and we wish to know how much (and which parts) of the curves are similar to this extent. The definition of the (one-sided and two-sided) Fr\'echet with shortcuts is practically used in cases where we have a pre-assumption that the curves are similar, up to the existence of (not too many) outliers, and we want to estimate the magnitude of this similarity, eliminating the outliers.
Since we assume that the points are sampled along curves that we want to match, our algorithms are applicable to any scenario in which the continuous Fr\'echet with shortcuts is applicable.
Practical implementations of Fr\'echet distance algorithms that are made for experiments on real data in map matching applications, remove outliers from the data set ~\cite{CDGNW11,WSP06}.
In another map matching application, Brakatsoulas et
al.~\cite{BPSW05} define the notion of integral Fr\'echet distance to deal with outliers. This distance measure averages over
certain distances instead of taking the maximum.
Bereg et al.~\cite{BJWYZ08} and then Wylie and Zho~\cite{WZ13} considered the discrete Fr\'echet distance in biological conext, for protein (backbone) structure alignment and comparison. They use pair simplification of the protein backbones, that can be interpreted as making shortcuts while comparing them under the discrete Fr\'echet distance.

journal_version.tex
\documentclass[11pt,english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{float}
\usepackage{units}
\usepackage{textcomp}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{algorithm}
\usepackage[noend]{algorithmic}
\usepackage{caption}
\usepackage{subcaption}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\floatstyle{ruled}
\newfloat{algorithm}{tbp}{loa}
\providecommand{\algorithmname}{Algorithm}
\floatname{algorithm}{\protect\algorithmname}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.


\usepackage{latexsym}\@ifundefined{definecolor}
 {\usepackage{color}}{}
\usepackage{mathtools}\usepackage{amsthm}\usepackage{epsfig}\usepackage{algorithmic}\usepackage{wasysym}\usepackage{wrapfig}\usepackage{appendix}\usepackage{fancyhdr}\usepackage{enumerate}
\usepackage{times,euscript}
%\setlength{\textwidth}{6.0in}
%\setlength{\evensidemargin}{0.25in}
%\setlength{\oddsidemargin}{0.25in}
%\setlength{\textheight}{9.0in}
%\setlength{\topmargin}{-0.5in}
%
%\setlength{\baselineskip}{1.7\baselineskip}

\usepackage{fullpage}

\def\reals{{\mathbb R}}
\def\eps{{\varepsilon}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\D{{\cal D}}
\def\F{{\cal F}}
\def\K{{\cal K}}
\def\L{{\cal L}}
\def\M{{\cal M}}

\def\S{{\cal S}}
\def\varphiup{ \Phi}

\def\layer{L}
\def\layerarr{\L}
\def\block{B}
\def\blockarr{\B}
\def\bd{{\partial}}

\def\marrow{\marginpar[\hfill$\longrightarrow$]{$\longleftarrow$}}
%\def\rinat#1{\textsc{(Rinat says: }\marrow\textsf{#1})}
%\def\matya#1{\textsc{(Matya says: }\marrow\textsf{#1})}
%\def\micha#1{\textsc{(Micha says: }\marrow\textsf{#1})}
%\def\haim#1{\textsc{(Haim says: }\marrow\textsf{#1})}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{observation}[theorem]{Observation}

\newcommand{\MyFrame}[1]{\noindent \framebox[\textwidth]{ \begin{minipage}{0.97\textwidth} #1 \end{minipage}}}%

\def\paragraph#1{\medskip\noindent\textbf{#1}}

\makeatother

\usepackage{babel}

\date{}
\begin{document}
\begin{titlepage}
%\title{The Discrete and the Semi-Continuous Fr\'echet Distance with Shortcuts}
\title{The Discrete and Semi-continuous Fr\'echet Distance with Shortcuts\\ via Approximate Distance Counting and Selection\thanks{Work by Omrit Filtser has been partially supported by the Lynn and William Frankel Center for Computer Sciences.
Work by Haim Kaplan has been supported by Israel Science Foundation grant no. 822-10, and
German-Israeli Foundation for Scientific Research and Development (GIF) grant no. 1161/2011, and Israeli Centers of Research Excellence (I-CORE) program, (Center  No. 4/11).
Work by M. Katz has been partially supported by grant 1045/10 from the Israel Science Foundation, and by grant 2010074 from the United States -- Israel Binational Science Foundation.
Work by Micha Sharir has been supported 
by Grant 892/13 from the Israel Science Foundation, 
by the Israeli Centers of Research Excellence (I-CORE)
program (Center No.~4/11),
and by the Hermann Minkowski--MINERVA Center for Geometry at Tel Aviv
University.
Work by Micha Sharir and Rinat Ben Avraham has been supported 
by Grant 2012/229 from the U.S.-Israeli Binational Science Foundation.
A preliminary version of this paper has been accepted to SOCG'14~\cite{BFKKS13}.}}



\author{Rinat Ben Avraham%
\thanks{School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel;
\texttt{rinatba@gmail.com}%
} \and Omrit Filtser%
\thanks{Department of Computer Science, Ben-Gurion University, Beer-Sheva 84105, Israel; \texttt{omritna@post.bgu.ac.il}%
} \and Haim Kaplan%
\thanks{School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel;
\texttt{haimk@post.tau.ac.il}%
} \and Matthew J. Katz%
\thanks{Department of Computer Science, Ben-Gurion University, Beer-Sheva 84105, Israel; \texttt{matya@cs.bgu.ac.il}%
} \and Micha Sharir%
\thanks{School of Computer Science, Tel Aviv University, Tel~Aviv 69978,
Israel; \texttt{michas@post.tau.ac.il }%
} }

\maketitle




\input{abstract1.tex}
\end{titlepage}
\input{introduction.tex}
\input{discrete_shortcuts.tex}


\end{document}

semi_continuous1.tex


\section{Semi-continuous Fr\'echet distance with shortcuts}

\label{sec:semi_cont} Let $f\subseteq\mathbb{R}^{2}$ denote a
polygonal curve with $n$ edges $e_1,\ldots, e_n$ and $n+1$ vertices
$p_0,p_1,\ldots,p_n$, and let $A=(a_{1},\ldots,a_{m})$ denote a
sequence of $m$ points in the plane. Consider a person that is
walking along $f$ from its starting endpoint to its final endpoint,
and a frog that is jumping along the sequence $A$ of stones. The
frog is allowed to make shortcuts (i.e., skip stones) as long as it
traverses $A$ in the right (increasing) direction, but the person
must trace the complete curve $f$ (see Figure~\ref{fig:hdfd}(a)).
Assuming that the person holds the frog by a leash, our goal is to
compute the minimal length $\delta_F^s(A, f)$ of a leash that is
required in order to traverse $f$ and (parts of) $A$ in this manner,
taking the frog and the person from $(a_1,p_0)$ to $(a_m,p_n)$.

\begin{figure}[htb]
 \centering \includegraphics[scale=0.8]{HDFD.pdf}
\caption{\small (a) A curve $f$ and a sequence of points $A=(a_{1},\ldots,a_{5})$.
(b) Thinking of $f$ as a continuous mapping from $[0,1]$ to $\mathbb{R}^2$, the $i$th row depicts the set $\{t \in [0,1] \mid f(t) \in D_\delta(a_i)\}$. The
dotted subintervals and their connecting upward moves (not drawn) constitute the lowest semi-sparse staircase between the starting and final positions.}
\label{fig:hdfd}
\end{figure}


Consider the decision version of this problem, where, given a
parameter $\delta>0$, we wish to decide whether the person and the
frog can traverse $f$ and (parts of) $A$ using a leash of length
$\delta$. This problem can be solved using the algorithm for solving
the one-sided DFDS, with a slight modification that takes into account
the continuous nature of $f$. Specifically, for a
point $p \in \mathbb{R}^2$, let $D_\delta(p)$ denote the disk of
radius $\delta$ centered at $p$.
%Think of $f$ as the image of a continuous function $\alpha:[0,1] \rightarrow \mathbb{R}^2$.
Now, consider a vector $M$ whose entries correspond to the points of $A$. For each $i=1,\ldots,m$, the $i$th entry of $M$ is
%$$M_i = M(a_i) =\{t\in[0,1]\mid \alpha(t)\in D_\delta(p)\}$$
$$M_i = M(a_i) = f \cap D_\delta(a_i)$$
%\rinat{why not using the same reparameterization $\alpha$ of the introduction?}
(see Figure~\ref{fig:hdfd}(b)). Each $M_i$ is a finite union of connected subintervals of $f$.
We do not compute $M$ explicitly, because the overall ``description complexity'' of its entries might be too large.
Specifically, the number of connected subsegments of the edges of $f$ that comprise the elements of $M$ can be $mn$ in the worst case.

Instead, we assume availability of (efficient implementations of) the following two primitives.
\begin{enumerate}[(i)]
\item \label{enu:1}
{\bf NextEndpoint($x, a_i$):} Given a point $x\in f$ and a point $a_i$ of $A$, such that $x\in D_\delta(a_i)$,
 return the forward endpoint of the connected component of $f\cap D_\delta(a_i)$ that contains $x$.
\item \label{enu:2}
{\bf NextDisk($x,a_i$):}
Given $x$ and $a_i$, as in (\ref{enu:1}), find the smallest $j>i$ such that $x\in D_\delta(a_j)$,
or report that no such index exists (return $j =\infty$).
\end{enumerate}

Both primitives admit
efficient implementations. For our purposes it is sufficient to
implement Primitive (\ref{enu:1}) by traversing the edges of $f$ one
by one, starting from the edge containing $x$, and checking for each
such edge $e_j$ of $f$ whether the forward endpoint $p_j$ of $e_j$ belongs
to $D_\delta(a_i)$. For the first $e_j$ for which this test fails,
we return the forward endpoint of the interval $e_j \cap D_\delta(a_i)$. It is
also sufficient to implement Primitive (\ref{enu:2}) by checking for
each $j>i$ in increasing order, whether $x \in D_\delta(a_j)$, and
return the first $j$ for which this holds. To solve the decision
problem, we proceed as in the decision procedure of the one-sided
DFDS (see Figure~\ref{alg:semi-sparse}), except that when we move
``right'', we move along $f$ as long as we can within the current
disk (using Primitive (\ref{enu:1})), and when we move ``up'', we
move to the first following disk that contains the current point of
$f$ (using Primitive (\ref{enu:2})). More precisely, we use the
 decision procedure $\Gamma$ given in Figure~\ref{alg:semi-continuous}.

\begin{figure}[htbp]
\MyFrame{
\smallskip
\begin{itemize}
{\small \sf
\item \textbf{Input:} $A, f, \delta$ \vspace{-0.3cm}
\item $S\leftarrow \emptyset$ \vspace{-0.3cm}
\item $a^1\leftarrow a_1$, $x^1 \leftarrow p_0$ \vspace{-0.3cm}
\item If ($x^1 \notin D_\delta(a^1)$) then \vspace{-0.3cm}
    \begin{itemize}
    \item Return $\delta_F^s(A,f)>\delta$ \vspace{-0.3cm}
    \end{itemize}
\item Add $(a^1,x^1)$ to $S$ \vspace{-0.3cm}
\item $k \leftarrow 1$ \vspace{-0.3cm}
\item While ($a^k$ is not $a_m$ or $f$ is not fully traversed) do \vspace{-0.3cm}
    \begin{itemize}
          \item $x^{k+1} \leftarrow$ {\bf NextEndpoint($x^k, a^k$)} \vspace{-0.1cm}
          \item Add $(a^k, x^{k+1})$ to $S$ \vspace{-0.1cm}
          \item If ($a^k=a_m$ and $x^{k+1}=p_n$) then \vspace{-0.1cm}
          \begin{itemize}
               \item Return $\delta_F^s(A,f)\leq\delta$ \vspace{-0.1cm}
          \end{itemize}
          \item $l \leftarrow$ {\bf NextDisk($x^{k+1}, a^k$)} \vspace{-0.1cm}
          \item If ($ l \leq m$) then \vspace{-0.1cm}
          \begin{itemize}
            \item $a^{k+1} \leftarrow a_l$ \vspace{-0.1cm}
            \item Add $(a^{k+1}, x^{k+1})$ to $S$ \vspace{-0.2cm}
          \end{itemize}
          \item Else
            \begin{itemize}
            \item Return $\delta_F^s(A,f)>\delta$ \vspace{-0.2cm}
            \end{itemize}
          \item $k \leftarrow k+1$ \vspace{-0.3cm}
    \end{itemize}
\item Return $\delta_F^s(A,f)\leq\delta$
}
\end{itemize}
}\caption{The decision procedure $\Gamma$ for the semi-continuous Fr\'echet distance with shortcuts.} \label{alg:semi-continuous}
\end{figure}


The path $S$ computed by $\Gamma$ is a sequence of reachable
positions $(a^1, x^1), (a^2, x^2),\ldots$, where $a^k$ is a point of
$A$ and $x^k$ is a point on an edge of $f$. Let $P$ be the sequence
of pairs $(a^1,s^1), (a^2,s^2),\ldots$, where $s^k$ is either the edge 
of $f$ containing $x^k$ (in its relative interior) or the vertex of $f$ 
coinciding with $x^k$, for $k=1,2,\ldots$.\footnote{%
  Note that we use superscripts $a^k$ and $s^k$ to denote the 
  sequence $S$ defining the solution produced by the decision 
  procedure. This is to distinguish them from $a_k$
and $e_k$ or $p_k$, with subscripts, that denote the original input sequence
of points of the frog and the sequence of segments and their endpoints on $f$.}


The correctness of the decision procedure $\Gamma$ is proved
similarly to the correctness of the decision procedure of the one-sided
DFDS (of Figure~\ref{alg:semi-sparse}). More specifically, here
a \emph{semi-continuous semi-sparse staircase} is an interweaving
sequence of \emph{discrete skipping upward moves} and
\emph{continuous right moves}, where a discrete skipping upward move
is a move from a reachable position $(a_i,p)$ of the frog and the
person to another position $(a_j,p)$ such that $j>i$ and $p \in D_\delta(a_j)$. 
A continuous right move is a move from a reachable position $(a_i,p)$ of 
the frog and the person to another position $(a_i,p')$ where 
$p'$, and the entire portion of $f$ between $p$ and $p'$, are contained in $D_\delta(a_i)$. Then there exists a semi-continuous
semi-sparse staircase that reaches the position $(a_m, p_n)$ if and only
if $\delta^s_F(A,f) \le \delta$.

Concerning correctness, we prove
that if there exists a semi-continuous semi-sparse staircase $S'$ that
reaches position $(a_m, p_n)$, then the decision procedure
maintains a partial semi-continuous semi-sparse staircase $S$ that is
always ``below'' $S'$ (in terms of the corresponding indices of the positions of the frog), and therefore $S$ reaches a position where the person is at $p_n$ (and the frog can then jump directly to $a_m$). Intuitively, this holds since the decision
procedure can at any point join the plot of $S'$ using a discrete
skipping upward move. The running time of this decision procedure is
$O(n+m)$ since we advance along $f$ at each step of Primitive
(\ref{enu:1}), and we advance along $A$ at each step of Primitive
(\ref{enu:2}), so our naive implementations of these primitives never back up along the path and sequence, and consequently take $O(m+n)$ time in total.



We thus obtain the following lemma.



\begin{lemma}
Given a polygonal curve $f$ with $n$ edges in the plane, a set $A$
of $m$ points in the plane, and a parameter $\delta>0$, we can
determine whether the semi-continuous Fr\'echet distance
$\delta^s_F(A,f)$ with shortcuts between $A$ and $f$ is at most
$\delta$, in $O(m+n)$ time, using $O(m+n)$ space.
\end{lemma}



\paragraph{The optimization procedure.}
We now use the decision procedure $\Gamma$ to find the optimal value
$\delta_F^s(A, f)$. To make the dependence on $\delta$ explicit, 
we denote, in what follows, the decision procedure for distance
$\delta$ by $\Gamma(\delta)$. The path $S$ computed by
$\Gamma(\delta)$, and each element $(a^k,x^k)$ of $S$, depend on
$\delta$, so we denote them by $S(\delta), a^k(\delta)$ and
$x^k(\delta)$, respectively. The sequence $P$ of pairs $(a^k, s^k)$, 
and each of its elements, also depend on $\delta$, 
so we denote $P$ by $P(\delta)$, and $s^k$ by $s^k(\delta)$. 
Of course, $\Gamma(\delta)$ might fail, i.e., report that
$\delta_F^s(A,f) > \delta$. In such a case, the path $S(\delta)$ 
and the sequence of pairs $P(\delta)$ consist of everything that 
was accumulated in them until $\Gamma(\delta)$ has terminated (that is, aborted). 
In particular, $S(\delta)$ does not end in this case at $(a_m, p_n)$.

The path $S(\delta_1)$ is {\em combinatorially different} from the
path $S(\delta_2)$, for $\delta_1, \delta_2>0$, if $P(\delta_1) \neq
P(\delta_2)$; otherwise, we say that $S(\delta_1)$ and
$S(\delta_2)$ are {\em combinatorially equivalent}.

We next argue that each critical value of $\delta$ where $S(\delta)$
changes combinatorially must be of one of the following two types:

\begin{enumerate}
\item\label{enum:pv}
The distance between a point of $A$ and a vertex of $f$ (point-vertex distance).
\item\label{enum:ppe}
For two points $p, q \in A$ and an edge $e$ of $f$, the distance between $p$ (or $q$) 
and the intersection of $e$ with the bisector of $p$ and $q$ (point-point-edge distance).
\end{enumerate}
See Figure~\ref{fig:critical} for an illustration.
We assume general position of the input, so as to ensure that these 
critical distances are all distinct.

\begin{figure}[htb]
\centering \includegraphics[scale=0.8]{critical_distances.pdf}
\caption{\small Two of the critical distances between $f$ and $A$. $\delta_1$ is a point-vertex distance between $a_4$ and $p_2$. $\delta_2$ is a point-point-edge distance between $a_1$, $a_3$ and $e_1$.}
\label{fig:critical}
\end{figure}

\begin{lemma}
Let $\delta$ be such that $S(\delta^-)$ is combinatorially different
from $S(\delta)$, for all $\delta^- < \delta$ and arbitrarily close to
$\delta$. Then $\delta$ is either a point-vertex distance or a
point-point-edge distance.
\end{lemma}
\begin{proof}
In what follows, we use $\delta^-$ to denote an arbitrary point from the neighborhood of $\delta$ mentioned in the lemma. Consider the point at which the executions of $\Gamma(\delta^-)$ and of $\Gamma(\delta)$ add a pair to $P(\delta^-)$ which is
different from the pair added to $P(\delta)$ (this includes the case 
in which we add a pair to only one of the sets $P(\delta^-)$, $P(\delta)$). 
If $(a_1,p_0)$
is in $P(\delta)$ but not in $P(\delta^-)$ then $\delta$ is the
distance between $a_1$ and $p_0$, a point-vertex distance. 
Otherwise, assume that the different pairs arose following a call 
to {\bf NextEndPoint($x^k,a^k$)}. Then
$x^{k+1}(\delta) =$ {\bf NextEndPoint($x^k(\delta),a^k(\delta)$)} and
$x^{k+1}(\delta^-) =$ {\bf NextEndPoint($x^k(\delta^-),a^k(\delta^-)$)}
belong to different edges / vertices of $f$. Note that $a^k(\delta) =
a^k(\delta^-)$ since this is the first call that causes a
discrepancy between $P(\delta)$ and $P(\delta^-)$.
A simple continuity argument implies that the disk of radius $\delta$
about $a^k(\delta)$ must contain a vertex of $f$, so $\delta$ is a point-vertex distance.

Finally assume that the first difference in the pairs added to
$P(\delta^-)$ and $P(\delta)$ occured following a call to {\bf NextDisk}($x^{k+1}, a^k$). 
Put $a_{\ell(\delta)} =$ {\bf NextDisk}$(x^{k+1}(\delta),a^k(\delta))$ and
$a_{\ell(\delta^-)} = $ {\bf NextDisk}$(x^{k+1}(\delta^-),a^k(\delta^-))$. 
As before, $a^k(\delta) = a^k(\delta^-)$ by our assumption.
Moreover, since $x^{k+1}(\delta)$ is not a vertex of $f$ (or else the previous call to {\bf NextEndPoint} would have produced different pairs at $\delta^-$ and at $\delta$), a simple continuity argument shows that $x^{k+1}(\delta^-)\rightarrow x^{k+1}(\delta) $as $\delta^-\uparrow \delta$. Assume that $\ell(\delta^-) \neq \ell(\delta)$. We claim that in this case $x^{k+1}(\delta)$ must lie on $\bd D_\delta(a_{\ell(\delta)})$ and on $\bd D_\delta(a_{\ell(\delta^-)})$, showing that $\delta$ is a point-point-edge distance. The first containment follows from the execution of {\bf NextEndPoint} at $x^k(\delta), a^k(\delta)$ with distance $\delta$. By the same reasoning, we also have $x^{k+1}(\delta^-)\in \bd D_{\delta^-}(a_{\ell(\delta^-)})$. As $\delta^- \uparrow \delta$, $x^{k+1}(\delta^-) \rightarrow x^{k+1}(\delta)$, and $\bd D_{\delta^-}(a_{\ell(\delta^-)}) \rightarrow \bd D_\delta(a_{\ell(\delta^-)})$ (in the Hausdorff sense), which implies that $x^{k+1}(\delta)\in \bd D_\delta(a_{\ell(\delta^-)})$, as claimed.
\end{proof}


Note that the distance between a point of $A$ and an edge of $f$ is
not a critical distance (unless it coincides with a
point-point-edge distance, which is ruled out anyway by our general 
position assumption); informally, this is because the appearance or 
disappearance of the small interval of intersection between the edge and the
corresponding disk has no effect on $S(\delta)$ (because there is no way to get to this interval that did not exist for $\delta^-$ too). Note also that not all triples 
of two points $p,q$ of $A$ and an edge $e$ of $f$ create a point-point-edge
critical event, since the bisector of $p$ and $q$ might not intersect $e$.

The following lemmas lead, in combination with the decision procedure 
given above, to an algorithm for the optimization problem that runs in
$O((m+n)^{2/3}m^{2/3}n^{1/3}\log(m+n))$ randomized expected time. The framework 
of the proof is similar to that of the discrete case.
Lemma~\ref{lem:semi_cont_finding_interval} shows that, given a
parameter $L>0$, we can find, with high probability, an interval 
$(\alpha,\beta]$ such that $\alpha < \delta^s_F(A,f) \leq \beta$ 
and $(\alpha,\beta]$ contains no more than $L$ critical distances, 
in $O(m^2n\log(m+n)/L+(m+n)\log(m+n))$ randomized expected time. Then,
Lemma~\ref{lem:semi_cont_searching_in_interval} shows that we can
find $\delta^s_F(A,f)$ within $(\alpha,\beta]$ in
$O((m+n)L^{1/2}\log(m+n))$ time. Choosing
$L=m^{4/3}n^{2/3}/(m+n)^{2/3}$, we obtain an algorithm that runs in
$O((m+n)^{2/3}m^{2/3}n^{1/3}\log(m+n))$ randomized expected time. The proof of
Lemma~\ref{lem:semi_cont_finding_interval} is different from that of
the analogous lemma for the discrete case (Lemma~\ref{lem:finding_interval}), and uses 
a generalization of a random sampling technique by Har-Peled and Raichel
(see~\cite{HR13}). The proof of
Lemma~\ref{lem:semi_cont_searching_in_interval} is similar to but more involved
than the proof of the analogous lemma (Lemma~\ref{lem:searching_in_interval}) for the discrete case.
%\micha{Fix the REFS to the lemmas.}

\begin{lemma}
\label{lem:semi_cont_finding_interval} 
Given a polygonal curve $f$ with $n$ edges and a set $A$ of $m$ points 
in the plane, and a parameter $L>0$, we can find an interval 
$(\alpha,\beta]$ that contains, with high probability, at most $L$ 
critical distances $\delta$, including $\delta^s_F(A,f)$, 
in $O(m^2n\log(m+n)/L+(m+n)\log(m+n))$ randomized expected time.
\end{lemma}
\begin{proof}
We generate a random sample of $cx$ triples of two points of $A$ and
an edge of $f$, where $x=(\binom{m}{2}n+mn)\log(m+n)/L$, and $c>1$ is 
a sufficiently large constant. We also sample $cx$ pairs of a
point of $A$ and a vertex of $f$. This will generate at most $2cx$
critical values of $\delta$ (some of the triples that we sample might
not contribute a critical value, as noted above).

We perform a binary search over the sampled critical values that actually 
arise, using the decision procedure $\Gamma$ to guide the search. 
This takes $O(m^2n\log(m+n)/L+(m+n)\log(m+n))$ time (using a
linear time median finding algorithm).

We claim that the interval $(\alpha,\beta]$ that this procedure generates contains, 
with high probability, at most $L$ (non-sampled) critical values of 
$\delta$, including $\delta^s_F(A,f)$. To see that, consider the set 
$U$ of the $L/2$ (defined) critical values that are smaller than 
$\delta^s_F(A,f)$ and closest to it, and denote by $u$ (resp., $v$) the number of point-vertex distances (resp., point-point-edge distances) amond them; thus $u+v = L/2$. The total number of triples and 
pairs that potentially (but not necessarily) define a critical value 
is $z=(\binom{m}{2}n+mn)$, of which ${m \choose 2} n$ define point-point-edge distances, and $mn$ define point-vertex distances. The probability that none of the $2cx$ 
triples and pairs that we sampled generate a critical value in $U$ is
at most
$$ 
\left(1-\dfrac{u}{{m \choose 2}n}\right)^{cx}\cdot 
\left(1-\dfrac{v}{mn}\right)^{cx} \leq e^{-cx\left(\dfrac{u}{{m \choose 2} n}+\dfrac{v}{mn}\right)} \leq e^{-cx \cdot\frac{u+v}{z}} = e^{-\frac{c}{2} \log(m+n)} = \dfrac{1}{(m+n)^{c/2}}.
$$
The same argument, with the same resulting probability bound,
applies for the set $U'$ of the $L/2$ (defined) critical values 
that are greater than $\delta^s_F(A,f)$ and closest to it.
Hence, the probability that we miss all the $L$ critical values 
in $U\cup U'$ is polynomially small (and can be made arbitrarily 
small by increasing $c$).
\end{proof}

The following lemma shows that we can find $\delta^s_F(A,f)$ 
within $(\alpha,\beta]$, in $O((m+n)L^{1/2}\log(m+n))$ time. Notice the high-level similarity with the discrete counterpart in Lemma~\ref{lem:searching_in_interval}.

\begin{lemma}
\label{lem:semi_cont_searching_in_interval}
Given a polygonal curve $f$ with $n$ edges in the plane, a set 
$A$ of $m$ points in the plane, and an interval
$(\alpha_0,\beta_0]\subset\reals$ that contains at most $L$ 
critical distances $\delta$ (including $\delta^s_F(A,f)$), 
we can find $\delta^s_F(A,f)$ in $O((m+n)L^{1/2}\log(m+n))$ 
(deterministic) time using $O(m+n)$ space.
\end{lemma}
\begin{proof}
For an edge $e$ of $f$ and two points $p,q\in e$, let $e(p,q]$ be the
subedge of $e$ starting at $p$ (not including $p$) and ending at
$q$, and let $\ell(e)$ denote the line containing $e$.

We simulate the decision procedure $\Gamma$ at the unknown value
$\delta^* = \delta^s_F(A,f)$. Each step of $\Gamma$ involves a call to
one of the procedures {\bf NextEndPoint} and {\bf NextDisk}.
The execution of each of these procedures consists of a sequence
of tests---the former procedure tests the current disk against a 
sequence of edges of $f$, for finding the first exit point from 
the disk, and the latter procedure tests the current point 
$x^{k+1}(\delta)$ against a sequence of disks centered at the points
of $A$, for finding the first disk (beyond the present disk) that contains the point.
Each such test generates a critical value $\delta_0$, and we check
whether $\delta_0$ lies outside $(\alpha_0,\beta_0]$, in which case we know
the (combinatorial nature of the) outcome of the test (in the procedure {\bf NextEndPoint}, the point
$x^{k+1}(\delta_0)$ itself varies continuously with $\delta_0$), and
we can proceed to the next test. If $\delta_0$ lies in $(\alpha_0,\beta_0]$,
we bifurcate, proceeding along two branches, 
one assuming that $\delta^* \le \delta_0$
and the other assuming that $\delta^* > \delta_0$.

These bifurcations generate a tree $T$.  At each node of $T$
we maintain a triple $(\tau, a^k, e^k(p,q])$, where
$\tau=(\alpha,\beta]$ is a range of possible values for $\delta^*$ (a subrange of $(\alpha_0,\beta_0]$).
Each such triple satisfies the following invariant. For each
$\delta \in \tau$ there exists a pair $(a^k(\delta),x^k(\delta))\in
P(\delta)$ such that $a^k(\delta)=a^k$ and $e^k(p,q]$
is the set of all points $x^k(\delta)$ for $\delta\in\tau$. In
particular, $q=x^k(\beta)$ and $p$ is the limit of $x^k(\alpha^+)$
where $\alpha^+ > \alpha$ approaches $\alpha$.

The process is initialized as follows.
Let $\alpha'$ be the distance between $a_1$ and $p_0$. Clearly
$\delta_F^s(A, f) \ge \alpha'$. We run the decision procedure at
$\alpha'$, and return $\delta_F^s(A, f) = \alpha'$ if the 
procedure finds a path to $(a_m,p_n)$. Otherwise we
initialize the root of $T$ with the triple 
$((\alpha', \infty],a_1,e_1(p_0,p_0])$.


For simplicity of presentation, we represent a single cycle of the
decision procedure (consisting of a call to {\bf NextEndPoint} 
followed by a call to {\bf NextDisk}) by two consecutive levels of $T$, each catering to the corresponding call.
Let $v$ be a node of $T$ that represents the situation at the beginning 
of such a cycle.  We now show how to construct the triples of the 
children and the grandchildren of $v$ from the triple
$(\tau=(\alpha,\beta], a^k, e^k(p,q])$ of $v$. 

To construct the
children of $v$ we simulate {\bf NextEndPoint} assuming that the current pair in $S$ is $(a^k,x^k(\delta))$ for $\delta \in \tau$ and $x^k(\delta)\in e^k(p,q)$. The idea is to compute, for $\delta=\alpha$ and for $\delta=\beta$, the edge containing the forward endpoint of the connected component of $f \cap D_\delta(a^k)$ that contains $x^k(\delta)$. If we obtain the same edge $e$ for $\delta=\alpha$ and for $\delta=\beta$, we conclude that all values in $\tau$ agree that $(a^k, e)$ is the next pair in $P$ and we continue to the next step of the procedure. Otherwise, we have detected a critical value $\delta_0$ in $\tau$ and we bifurcate, proceeding along two paths --- one assuming that $\delta^*\in (\alpha,\delta_0]$ and one assuming that $\delta^*\in (\delta_0,\beta]$. 

We now give a more detailed description of the simulation of {\bf NextEndPoint} at $v$.
Let $q_\alpha$ be the first intersection of $D_{\alpha}(a^k)$ with $f$ 
following $p=x^k(\alpha)$, and let $q_\beta$ be the first intersection 
of $D_{\beta}(a^k)$ with $f$ following $q=x^k(\beta)$. Let $e_j$ be the
edge of $f$ equal to $e^k$.  We traverse $e_j, e_{j+1},\ldots, e_n$ 
in order, and for each such segment $e_\ell$, we have three possible cases.

(i) $q_\alpha \notin e_\ell$ and $q_\beta \notin e_\ell$.
In this case, the forward endpoint
$x^{k+1}(\delta)$ of the connected component $f\cap D_{\delta}(a^k)$ 
containing $x^k(\delta)$ is not in $e_\ell$, for all
$\delta \in \tau$. So we proceed to the next edge $e_{\ell+1}$.

(ii) ${q_\alpha \in e_\ell}$ and ${q_\beta \in e_\ell}$.
In this case, $e_{\ell}(q_\alpha, q_\beta]$ is the set of all the 
forward endpoints $x^{k+1}(\delta)$ of the connected components 
of $f \cap {D_{\delta}(a^k)}$ containing $x^{k}(\delta)$, for 
$\delta\in\tau$. In this case $v$ has a single child $v'$, with
the triple $(\tau=(\alpha,\beta], a^k, e_\ell(q_\alpha,q_\beta])$.

(iii) ${q_\alpha \in e_\ell}$ and ${q_\beta \notin e_\ell}$.
In this case, we encounter a point-vertex critical distance
$\delta_0 \in \tau$, between $a^k$ and $p_\ell$. That is, for each
$\delta\in (\delta_0,\beta]$, the forward endpoint of the connected
component $f\cap D_{\delta}(a^k)$ containing $x^k(\delta)$ is not in
$e_\ell$ (but in a segment beyond $e_\ell$), and for each 
$\delta\in (\alpha,\delta_0]$, the forward endpoint of the 
connected component $f\cap D_{\delta}(a^k)$ containing $x^k(\delta)$ 
is in $e_\ell(q_\alpha, p_\ell]$. We generate one child $v'$ of $v$ 
with the triple $((\alpha,\delta_0], a^k, e_\ell(q_\alpha,p_\ell])$,
and generate the other children of $v$ by proceeding to the 
following edge $e_{\ell+1}$ with the smaller range $(\delta_0, \beta]$,
replacing $q_\alpha$ with $p_\ell$, and continuing the process recursively,
generating a child for each consecutive segment in which we need to bifurcate.

Next we generate the grandchildren $v''$ of each child $v'$ of $v$,
which result from the simulation of the call to {\bf NextDisk}.
The idea is to compute, for $\delta=\alpha$ and for $\delta=\beta$, the next point $a_\ell$ of $A$ such that the disk $D_\delta(a_\ell)$ contains $x^k(\delta)$ (note that $x^k(\alpha)=p$ and $x^k(\beta)=q$). If we obtain the same point $a_\ell$ for $\delta=\alpha$ and for $\delta=\beta$, we conclude that all values in $\tau$ agree that $(a_\ell, e^k)$ is the next pair in $P$ and we continue to the next step of the procedure. Otherwise, we have detected a critical value $\delta_0$ in $\tau$ and we bifurcate, proceeding along two paths --- one assuming that $\delta^*\in (\alpha,\delta_0]$ and one assuming that $\delta^*\in (\delta_0,\beta]$. 

We now give the details of simulating {\bf NextDisk} at $v'$.
For that we use the following easy observation, whose trivial proof is omitted
(see Figure~\ref{fig:bisector} for an illustration).

\begin{observation}\label{obs}
Let $a$ and $b$ be two points in the plane, let $h$ be their bisector,
and let $s$ be a point on $\bd{D_\delta(a)}$, for some $\delta>0$. 
Then $s\in D_\delta(b)$ if and only if $s$ is in the halfspace 
bounded by $h$ that contains $b$.
\end{observation}


%\micha{I removed the really trivial proof.}

% \begin{proof}

% $s\in \bd{D_\delta(a)}$, so $\|s-a\|=\delta$.

% If $s\in D_\delta(b)$ then the distance $\|s-b\|$ is at most $\delta$. 

% Hence, $s$ is closer to $b$ than to $a$ (or $\|s-b\|=\|s-a\|$). It 

% follows that $s$ is in the halfspace bounded by $h$ that contains $b$.



% If $s$ is in the halfspace bounded by $h$ that contains $b$, then it is 

% closer to $b$ then to $a$ (or $\|s-b\|=\|s-a\|$). Thus $\|s-b\| \leq \delta$, 

% and so $s \in D_\delta(b)$. See Figure~\ref{fig:bisector}.

% \end{proof}



\begin{figure}[htb]
\centering \includegraphics[scale=0.6]{bisector}
\centering \caption{\small The points on $\bd{D_\delta(a)}$ that are in 
$D_\delta(b)$ are in the halfspace bounded by $h$ that contains $b$.}\label{fig:bisector}
\end{figure}

Let $v'$ be a child of $v$ corresponding to the triple
$(\tau=(\alpha,\beta], a^k, e^{k}(p,q])$, where $a^k$ is the point $a_i$. We
simulate {\bf NextDisk} at all possible $\delta \in \tau$ by traversing
$a_{i+1},\ldots, a_m$, distinguishing between the following cases at each such
point $a_\ell$.


% \label{enum:cant_jump}
(i) ${p \notin D_\alpha(a_{\ell})}$ and ${q \notin D_\beta(a_{\ell})}$.
In this case, each point $x^{k}(\delta) \in e^{k}(p,q]$, for 
$\delta \in(\alpha,\beta]$, satisfies
$x^{k}(\delta) \notin D_{\delta}(a_\ell)$. Indeed, by the way we
computed the triple for $v'$, $p$ is a point on $\bd{D_\alpha(a^k)}$
and $q$ is a point on $\bd{D_\beta(a^k)}$. Thus, by
Observation~\ref{obs}, $p$ and $q$ are not in the halfspace $h^+(a^k,a_l)$ bounded
by $h(a^k,a_\ell)$ that contains $a_\ell$, where $h(a^k,a_\ell)$ is
the bisector of $a^k$ and $a_\ell$. Thus, $x^{k}(\delta)$, for any
$\delta\in (\alpha,\beta]$, is also not in the halfspace $h^+(a^k,a_l)$. Since $x^{k}(\delta)$ is a
point on $\bd{D_{\delta}(a^k)}$, again by Observation~\ref{obs},
$x^{k}(\delta) \notin D_{\delta}(a_\ell)$. Hence, in this case, the
$A$-frog cannot jump to $a_\ell$ when the person is at $x^{k}(\delta)$
(for each point $x^{k}(\delta) \in e^{k}(p,q]$, over $\delta \in
(\alpha,\beta]$), so we proceed to the next point $a_{\ell+1}$.



% \label{enum:can_jump}
(ii) ${p \in D_\alpha(a_{\ell})}$ and ${q\in D_\beta(a_{\ell})}$.
By a similar reasoning to that of the preceding case,
each point $x^{k}(\delta) \in e^{k}(p,q]$
satisfies $x^{k}(\delta) \in D_{\delta}(a_\ell)$. Hence, for each
point $x^{k}(\delta)\in e^{k}(p,q]$ the $A$-frog can jump to
$a_{\ell}$ when the person is at $x^{k}(\delta)$.
So in this case $v'$ has only one child $v''$ that corresponds to
the triple $(\tau=(\alpha,\beta], a_\ell, e^{k}(p,q])$.
%\micha{Dont you mean that $v''$ is the ``terminal'' child of $v'$,

%because you may have passed through previous disks in which the first case applied?}




% \label{enum:bifurcate}
(iii) ${q \in D_\beta(a_{\ell})}$ and ${p \notin D_\alpha(a_{\ell})}$.
By a similar reasoning as in the previous
cases, using Observation~\ref{obs}, $q$ is in the halfspace
$h^+(a^k,a_l)$, and $p$ is not.
Thus, there exists a point $s$ such that $s = e^k(p,q] \cap h(a^k,a_\ell)$.
By the way we constructed the triple of $v'$, it follows that for
each point $p' \in e^k(p,q]$ there exists a $\delta \in (\alpha, \beta]$ 
such that $p'$ is $x^k(\delta)$ and $x^k(\delta) \in \bd D_{\delta}(a^k) \cap e^k$.

By observation \ref{obs} we have: (a) If
$x^k(\delta) \in e^k(p,s]$ then $x^k(\delta) \not\in
D_{\delta}(a_\ell)$ (so the frog cannot jump to $a_\ell$ when the
person is at $x^k(\delta)$). (b) If $x^k(\delta)\in
e^k(s,q]$ then $x^k(\delta)\in D_{\delta}(a_\ell)$ (so the frog can jump to
$a_\ell$ when the person is at $x^k(\delta)$).

Let $\delta_0=\|a^k-s\|=\|a_\ell-s\|$. Clearly, $x^k(\delta) \in
e^k(p,s]$ for $\alpha < \delta \le \delta_0$ and $x^k(\delta) \in
e^k(s,q]$ for $\delta_0< \delta \le \beta$. Furthermore, $\delta_0$
is a point-point-edge
critical value involving $a^k, a_\ell$ and $e^k$.

We generate a child $v''$ of $v'$ that corresponds to the triple
$((\delta_0, \beta], a_\ell, e^k(s,q])$, and continue to generate the
other children of $v'$ by proceeding to the next point (if there is
one) $a_{\ell + 1}$ with the updated triple $((\alpha, \delta_0],
a^k, e^k(p,s])$.  See Figure~\ref{fig:bifurcate}(a).
%\micha{Again, see my comment in the preceding case.}


% \label{enum:bifurcate2}
(iv) ${p\in D_\alpha(a_{\ell})}$ and ${q \notin D_\beta(a_{\ell})}$.
Arguing similarly to the preceding case,
we encounter a point-point-edge critical value $\delta_0$ involving
$a^k, a_\ell$ and $e^k$, where $\delta_0$ is the distance between 
$s = e^k(p,q] \cap h(a^k,a_\ell)$ and $a^k$ (or $a_\ell$).

We generate a child $v''$ of $v'$ that corresponds to the triple
$((\alpha, \delta_0], a_\ell, e^k(p,s])$, and continue to generate
the other children of $v'$ by proceeding to the next point (if there
is one) $a_{\ell + 1}$ with the updated triple $(( \delta_0,\beta],
a^k, e^k(s,q])$.  See Figure~\ref{fig:bifurcate}(b).

\begin{figure}
        \centering
        \begin{subfigure}[b]{0.4\textwidth}
                \centering
                \includegraphics[width=\textwidth]{bifurcate1}
                (a) $q \in D_\beta(a_{l})$ and $p \notin D_\alpha(a_{l})$.
                \label{fig:bifurcate1}
        \end{subfigure}%
 %add desired spacing between images, e. g. ~, \quad, \qquad etc.
          %(or a blank line to force the subfigure onto a new line)
\hspace{1cm}
        \begin{subfigure}[b]{0.4\textwidth}
                \centering
                \includegraphics[width=\textwidth]{bifurcate2}
                (b) $p \in D_\alpha(a_{l})$ and $q \notin D_\beta(a_{l})$.
                \label{fig:bifurcate2}
        \end{subfigure}

                \caption{\small Situations that cause bifurcation in when simulating a call to NextDisk.
The disks $D_{\delta_0}(a_{i})$ and $D_{\delta_0}(a_{l})$, where $\delta_0$ is the corresponding critical value, are drawn dashed. }\label{fig:bifurcate}
\end{figure}


Note that we may reach the last point $a_m$ without generating
children of $v'$ (i.e., grandchildren of $v$). In this case 
$\delta^*$ cannot be in $(\alpha, \beta]$, and we can abandon this branch.
When we reach a node whose triple is
$((\alpha, \beta], a_m, e_n(p,p_n])$ then if $\delta^* \in (\alpha,
\beta]$ then $\delta^* = \beta$.

It is straightforward to show that the triple of each node $v$
that we generate satisfies the invariant mentioned at the beginning
of the proof.

%
%
%
%\paragraph{Correctness:}

%Let $\delta$ be any value in $(\alpha,\beta]$. We prove that the input $(\tau, a^k, e^k[p,q])$, for which $\tau \ni \delta$, satisfies that $e^k[p,q]$ contains a point $x^k(\delta)$ such that $(a^k, x^k(\delta))$ is the pair added to $S(\delta)$ in the $k$th step of $\Gamma(\delta)$. Specifically $(a^k,p)$ (resp., $(a^k, q)$) is the pair added to $S(\alpha)$ (resp., $S(\beta)$) in the $k$th step of $\Gamma(\alpha)$ (resp., $\Gamma(\beta)$). The proof is by induction on $k$.

%For $k=1$, the pair added to $S(\delta)$ is $(a_1,p_0)$. We thus need to show that, for $\tau$ that contains $\delta$, the output of the first step is $(\tau, a_1, e_1[p,q])$ where $e_1[p,q]$ contains $p_0$. Indeed, the output of the first step is $(\tau, a_1, e_1[p_0,p_0])$ for all $\tau \subseteq (\alpha,\beta]$.

%We now show that the claim holds for the $k+1$ step assuming that it holds for the $k$th step.

%We consider two cases:

%\begin{enumerate}

%\item

%\textbf{The $k$th pair $(a^k, x^k(\delta))$ is added to $S(\delta)$ following a call of $\Gamma(\delta)$ to primitive(i).}

%In this case, the $k+1$ pair added to $S(\delta)$ is following a call of $\Gamma(\delta)$ to primitive(ii). Thus, the $k+1$ pair added to $S(\delta)$ is $(a_l, x^k(\delta))$, where $a_l$ is the first point following $a^k$ such that $D_\delta(a^k)$ contains $x^k(\delta)$.

%We thus need to show that the output triple $(\tau', a^{k+1}, e^{k+1}[p',q'])$ of the $k+1$ step of the optimization algorithm, for which $\tau'$ is the range containing $\delta$, is such that $a^{k+1}=a_l$ and $e^{k+1}[p',q']$ is a subedge of $e^k$ that contains $x^k(\delta)$.

%The $k+1$ step made by the optimization algorithm is a step of type (b).

%We proceed to the $k+2$ step of the optimization algorithm only when we find the first point $a_l$ such that $x^k(\delta) \in D_{\delta}(a_l)$ for each $\delta \in \tau'$.

%We then set $(\tau', a_l, e^k[p',q'])$ as input for the $k+2$ step. To see that $e^{k}[p',q']$ contains $x^k(\delta)$, note that if the algorithm did not bifurcate, then $\tau'=\tau$ and $p'=p, q'=q$, so $e^k[p,q]$ contains $x^k(\delta)$ by the induction hypothesis. Otherwise, either $\delta\in (\alpha,\delta_0]$ and $p'=p, q'=s$ or $\delta\in (\delta_0,\beta]$ and $p'=s, q'=q$, where $s = e^k[p,q] \cap h(a^k,a_l)$ and $\delta_0=\|a^k-s\|=\|a_l-s\|$. The first case corresponds to case~\ref{enum:bifurcate2} of type-(b)-step and the second case corresponds to case~\ref{enum:bifurcate} of type-(b)-step. In both cases $s$ is on the boundary of $D_{\delta_0}(a^k)$. In the first case, by the induction hypothesis $p$ is on the boundary of $D_{\alpha}(a^k)$. Thus, the boundary of $D_{\delta}(a^k)$ intersects $e^k(p,s)$. Since $(a^k, x^k(\delta))$ was added to $S$ following a call to primitive (i), $x^k(\delta)$ is on the intersection of $\bd D_\delta(a^k)$ with $e^k$, and thus $x^k(\delta)$ is in $e^k(p,s)$ as claimed. Arguing similarly for the second case, we get that if

%$\delta\in(\delta_0,\beta]$, then $x^k(\delta) \in e^k(s,q)$.

%

%\item

%\textbf{The $k$th pair $(a^k, x^k(\delta))$ is added to $S(\delta)$ following a call of $\Gamma(\delta)$ to primitive(ii).}

%In this case, the $k+1$ pair added to $S(\delta)$ is following a call of $\Gamma(\delta)$ to primitive(i). Thus, the $k+1$ pair added to $S(\delta)$ is $(a^k, u)$, where $u$ is the forward endpoint of $e_l\cap D_\delta(a^k)$ and $e_l$ is the first edge after $e^k$ that is not fully contained in $D_\delta(a^k)$. We thus need to show that the output triple $(\tau', a^{k+1}, e^{k+1}[p',q'])$ of the $k+1$ step of the optimization algorithm, for which $\tau'$ is the range containing $\delta$, is such that $a^{k+1}=a^k$ and $e^{k+1}[p',q']$ is a subedge of the first $e_l$ that contains the forward endpoint of $e_l\cap D_\delta(a^k)$.

%The $k+1$ step made by the optimization algorithm is a step of type (a).

%If the algorithm does not bifurcate in this step, then $\tau' =\tau$ and we proceed to the $k+2$ step of the optimization algorithm only when we find the first edge $e_l$ after $e^k$ such that the forward endpoint $p'$ of $D_{\alpha}(a^k) \cap \ell(e_l)$ and the forward endpoint $q'$ of $D_{\beta}(a^k) \cap \ell(e_l)$ are in $e_l$. In this case, $x^{k+1}(\delta) =\bd D_{\delta}(a^k) \cap e_l$ is in $e_l[p',q']$ as required.

%If the algorithm bifurcates, we proceed to the $k+2$ step of the optimization algorithm only if $\delta \in (\alpha,\delta_0)$ where $\delta_0= \|a^k-p_l\|$. In this case, $p_l \in \bd D_{\delta_0}(a^k)$ and $p' =\bd D_{\alpha}(a^k)\cap e_l$. Hence, $e_l[p',p_l]$ contains $x^{k+1}(\delta)= \bd D_{\delta}(a^k)\cap e_l$, as claimed.

%

%\end{enumerate}





We do not generate the entire tree $T$ but proceed as in
Lemma~\ref{lem:searching_in_interval}. We distinguish between unary
nodes $v\in T$, each having a single child, and nodes $v\in T$ with
more than one child. A node $v$ with $d>1$ children is associated
with $d-1$ critical events that triggered these $d-1$
bifurcations. We construct the relevant subtree $T'$ of $T$ top down,
and we stop expanding a node $v\in T'$ if it has $s$ unary immediate ancestors. 
We stop expanding $T'$ altogether when it contains $m+n$ nodes or when each of
its leaves has $s$ unary immediate ancestors.
Note that we might stop the construction of $T'$ in the middle of the expansion of a node $v$ that has too many children. In that case, if $v$ happens to be the node with the range containing $\delta^*$, we either resume the procedure from one of the children already constructed, or abandon them and construct the remaining children.

We then run a binary
search over the set of $O(m+n)$ critical values that we have
accumulated at the bifurcations of $T'$, using the decision procedure
$\Gamma$ to guide the search. This determines the leaf $v$ of $T'$
such that the range $\tau$ of $v$ contains $\delta^*$. The path of $T'$ leading to $v$ is the next portion of the semi-sparse path $S$ produced by the decision procedure (in Figure~\ref{alg:semi-continuous}) at $\delta^*$. We then repeat the whole procedure starting at $v$. We stop when we reach a node that records the last step of $S$, which reaches $(a_m,p_n)$, and the final range $(\alpha,\beta]$ of that node yields $\delta^*=\beta$. An analysis analogous to the one in
Lemma~\ref{lem:searching_in_interval} shows that this algorithms
runs in $O((m+n)L^{1/2}\log(m+n))$ time using $O(m+n)$ space.
\end{proof}

By combining Lemma~\ref{lem:semi_cont_finding_interval} with Lemma~\ref{lem:semi_cont_searching_in_interval} as noted above, we obtain the following result.



\begin{theorem}
Given a set $A$ of $m$ points and a polygonal curve $f$ with $n$ edges in the plane, we can compute the one-sided semi-continuous Fr\'echet distance $\delta_F^s(A,f)$ with shortcuts in randomized expected time $O((m+n)^{2/3}m^{2/3}n^{1/3}\log(m+n))$ using $O((m+n)^{2/3}m^{2/3}n^{1/3})$ space.
\end{theorem}



1310.5245.extracted_bib
\begin{thebibliography}{}

\bibitem{ABKS12} P.~K.~Agarwal, R.~Ben Avraham, H.~Kaplan and
M.~Sharir, Computing the discrete Fr\'echet distance in subquadratic
time, \textit{Proc. 24th Annu. ACM-SIAM Sympos. Discrete Algorithms}
(2013), 156--167. Also in \textit{SIAM J. Comput.}, in press, and in arxiv:1204.5333 (2012).

\bibitem{AG95} H.~Alt and M.~Godau, Computing the Fr\'echet distance
between two polygonal curves, \textit{Internat. J. Comput. Geom. Appl.}
5 (1995), 75--91.

%\bibitem{AKW04} H.~Alt, C.~Knauer and C.~Wenk, Comparison of distance
%measures for planar curves, \textit{Algorithmica} 38(1) (2004), 45--58.

%\bibitem{AHKWW06} B.~Aronov, S.~Har-Peled, C.~Knauer, Y.~Wang
%and C.~Wenk, Fr\'echet distance for curves, revisited, \textit{Proc.
%14th Annu. European Sympos. Algorithms} (2006), 52--63.

\bibitem{BFKKS13}
R.~Ben Avraham, O.~Filtser, H.~Kaplan, M.~J.~Katz and M.~Sharir,
The Discrete and Semicontinuous Fr\'echet Distance with Shortcuts via Approximate Distance Counting and Selection, \textit{Proc. 30th ACM Sympos. Comput. Geom.} (2014), to appear.  arxiv:1310.5245 (2013).

\bibitem{BJWYZ08}
S.~Bereg, M.~Jiang, W.~Wang, B.~Yang and B.~Zhu,
Simplifying 3d polygonal chains under the discrete Frechet distance,
\textit{Proc. 8th Latin American Conf. on Theoretical informatics} (2008), 630--641.

\bibitem{BS02}
S.~Bespamyatnikh and M.~Segal,
Fast algorithms for approximating distances,
\textit{Algorithmica} 33(2) (2002), 263--269.

\bibitem{BPSW05} S.~Brakatsoulas, D.~Pfoser, R.~Salas and C.~Wenk,
On map-matching vehicle tracking data, \textit{Proc. 31st Intl. Conf.
Very Large Data Bases} (2005), 853--864. 

\bibitem{BBG08} K.~Buchin, M.~Buchin and J.~Gudmundsson, Detecting
single file movement, \textit{Proc. 16th ACM SIGSPATIAL Intl. Conf.
Adv. GIS} (2008), 288--297.

\bibitem{BBGLL08} K.~Buchin, M.~Buchin, J.~Gudmundsson, M.~L\'effler
and J.~Luo, Detecting commuting patterns by clustering subtrajectories,
\textit{Internat. J. Comput. Geom. Appl.} 21(3) (2011), 253--282. 

\bibitem{BBMM12} K.~Buchin, M.~Buchin, W.~Meulemans and W.~Mulzer,
Four soviets walk the dog --- with an application to Alt's conjecture,
\textit{Proc. 25th Annu. ACM-SIAM Sympos. Discrete Algorithms} (2014), 1399--1413.

\bibitem{BBW09}
K.~Buchin, M.~Buchin and Y.~Wang,
Exact algorithms for partial curve matching via the Fr\'echet distance,
\textit{Proc. 20th Annu. ACM-SIAM Sympos. Discrete Algorithms} (2009), 645--654.

\bibitem{BDS13}
M.~Buchin, A.~Driemel and B.~Speckmann,
Computing the Fr\'echet distance with shortcuts is NP-hard,
\textit{Euro. Workshop Comput. Geom.} (2013), 43--46.

\bibitem{Cha93}
B.~Chazelle,
Cutting hyperplanes for divide-and-conquer,
\textit{Discrete Comput. Geom.} 9 (1993), 145--158.

\bibitem{CF90}
B.~Chazelle and J.~Friedman,
A deterministic view of random sampling and its use in geometry,
\textit{Combinatorica} 10 (1990), 229--249.

\bibitem{CDGNW11} D.~Chen, A.~Driemel, L.~J.~Guibas, A.~Nguyen
and C.~ Wenk, Approximate map matching with respect to the Fr\'echet
distance, \textit{Proc. 7th Workshop on Algorithm Engineering and
Experiments} (2011), 75--83.


\bibitem{DH12} A.~Driemel and S.~Har-Peled, Jaywalking your dog:
Computing the Fr\'echet distance with shortcuts, \textit{SIAM J. Comput.} 42(5) (2013), 1830--1866. 

%\bibitem{DHW10} A.~Driemel, S.~Har-Peled and C.~Wenk, Approximating
%the Fr\'echet distance for realistic curves in near linear time, \textit{Discrete Comput. Geom.} %48(1) (2012), 94--127. 

\bibitem{EM94} T.~Eiter and H.~Mannila, Computing discrete Fr\'echet
distance, Technical Report CD-TR 94/64, Christian Doppler Laboratory
for Expert Systems, TU Vienna, Austria, 1994.

\bibitem{HR13}
S.~Har-Peled and B.~Raichel,
Net and prune: a linear time algorithm for Euclidean distance problems,
\textit{Proc. 45th ACM Sympos. Theory Comput.} (2013), 605--614.

\bibitem{HS11}
S.~Har-Peled and M.~Sharir,
Relative $(p, \eps)$-approximations in geometry,
\textit{Discrete Comput. Geom.} 45(3) (2011), 462--496.

\bibitem{KS97} M.~J.~Katz and M.~Sharir, An expander-based approach
to geometric optimization, \textit{SIAM J. Comput.} 26(5) (1997),
1384--1408.

\bibitem{KKS05} M.~S.~Kim, S.~W.~Kim and M.~Shin, Optimization
of subsequence matching under time warping in time-series databases,
\textit{Proc. ACM Sympos. Applied Comput.} (2005), 581--586.

\bibitem{KHMTC98} S.~Kwong, Q.~H.~He, K.~F.~Man, K.~S.~Tang
and C.~W.~Chau, Parallel genetic-based hybrid pattern matching algorithm
for isolated word recognition, \textit{Intl. J. Pattern Recog. Art.
Intel.} 12(5) (1998), 573--594.

\bibitem{LLS01}
Y.~Li, P.~M.~Long and A.~Srinivasan,
Improved bounds on the sample complexity of learning,
\textit{J. Comput. Syst. Sci.} 62 (2001), 516--527.

\bibitem{Mat91}
J.~Matou\v{s}ek,
Cutting hyperplane arrangements,
\textit{Discrete Comput. Geom.}
6 (1991), 385--406.

\bibitem{MP99} M.~E.~Munich and P.~Perona, Continuous dynamic
time warping for translation-invariant curve alignment with applications
to signature verification, \textit{Proc. 7th Intl. Conf. Comp. Vision}
(1999), 108--115.


\bibitem{ShSh}
M.~Sharir and H.~Shaul,
Semialgebraic range reporting and emptiness searching with applications,
\textit{SIAM J. Comput.} 40(4) (2011), 1045--1074.

\bibitem{WSP06} C.~Wenk, R.~Salas and D.~Pfoser, Addressing the
need for map-matching speed: Localizing global curve-matching algorithms,
\textit{Proc. 18th Intl. Conf. Scientific and Statistical Database
Management} (2006), 379--388. %\bibitem{SH76}

\bibitem{WZ13}
T.~Wylie and B.~Zhu,
Protein chain pair simplification under the discrete Frechet distance,
\textit{IEEE/ACM Trans. Comput. Biology Bioinform.} (2013), 1372--1383.

\end{thebibliography}