\documentclass[12pt]{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
\usepackage {graphicx}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator {\emst}{emst}
\DeclareMathOperator {\conv}{CH}
\DeclareMathOperator {\argmin}{argmin}
\DeclareMathOperator {\DT}{DT}
\DeclareMathOperator {\UC}{UC}
\DeclareMathOperator {\LC}{LC}

\newtheorem {theorem}{Theorem}[section]
\newtheorem {problem}[theorem] {Problem}
\newtheorem {lemma}[theorem] {Lemma}
\newtheorem {observation}[theorem] {Observation}
\newtheorem {corollary}[theorem] {Corollary}
\newtheorem {claim}[theorem] {Claim}


\title{Shortest Paths in Polygons}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Properties of Shortest Paths}

We are given a simple polygon $P$, and two points $s$ and $t$ inside $P$.
Let $V(P)$ be the vertex set of $P$, and $E(P)$ the edge set. 
We assume that no three points
from $V(P) \cup \{s, t\}$ are on a line.
We would like to find a shortest path from $s$ to $t$ that lies inside
$P$, i.e., a shortest polygonal chain $\pi$ with endpoints $s$ and
$t$ such that $\pi \subseteq P$. Let $V(\pi)$ denote the vertices and
$E(\pi)$ the edges of $\pi$.
Every vertex in $V(\pi) \setminus \{s,t\}$ is called an \emph{inner vertex}
of $\pi$.

\begin{lemma}\label{lem:polyVert}
  There is a shortest path $\pi$ from $s$ to $t$ so that
  all inner vertices of $\pi$ are vertices of $P$.
\end{lemma}

\begin{proof}
  Let $\pi$ be a shortest path from $s$ to $t$ with a minimum number of 
  inner vertices not in $V(P)$. If no such vertices exist,
  we are done. Thus, suppose there is
  $v \in V(\pi) \setminus (V(P) \cup \{s,t\})$,
  and let $e_1, e_2 \in E(\pi)$ be the two edges of $\pi$ incident on
  $v$. If $e_1$ and $e_2$ are collinear, then $v$ can be deleted from
  $\pi$, contradicting the fact that the number of inner vertices 
  is minimum.
  
  Suppose that $v$ is in the interior of an 
  edge $f \in E(P)$.
  There is an $\eps > 0$ such that the $\eps$-ball $B = B(v, \eps)$ around
  $v$ intersects only $v$,  $e_1$, $e_2$, and the interior of $f$.
  Let $w_1$ and $w_2$ be the intersections of $\partial B$
  with $e_1$ and $e_2$. Since $B$ intersects the polygon boundary
  only in $f$, the line segment $w_1w_2$ lies in $P$. Also,
  since $e_1$ and $e_2$ are not collinear, the segment
  $w_1w_2$ is strictly shorter than the chain $w_1vw_2$.
  Thus, replacing $w_1vw_2$ by the
  segment $w_1w_2$ yields a strictly shorter path from $s$ to
  $t$, a contradiction to $\pi$ being a shortest path; see
  Fig.~\ref{fig:polyInnerVert}.

  \begin{figure}
    \centering
    \includegraphics{polyInnerVert}
    \caption{If $v$ lies in the interior of $f$, we can
      shortcut $\pi$ along $w_1 w_2$.}
      \label{fig:polyInnerVert}
  \end{figure}
  The case that $v$ lies in the interior of $P$ is analogous.
\end{proof}

Now let $\pi$ be a shortest path from $s$ to $t$ with all inner vertices
in $V(P)$.
Let $e_1, e_2 \in E(\pi)$ be the edges of $\pi$ incident on $v \in V(P)$.
The \emph{inner angle} of $\pi$ at $v$ is the angle between $e_1$ and
$e_2$ at $v$ that lies wholly in $P$.
We say that $v$ is a \emph{reflex vertex} of $\pi$ if the inner angle 
is at least $180^\circ$, see Fig.~\ref{fig:polyInnerAng}(a,b).

\begin{figure}
\centering
\includegraphics{polyInnerAng}
\caption{The inner angle $\alpha$ of $\pi$ at $v$: (a) $v$ is not
reflex; (b) $v$ is reflex; (c) if $v$ is not reflex, we can
shortcut $\pi$ at $w_1w_2$.}
\label{fig:polyInnerAng}
\end{figure}

\begin{lemma}
  Let $\pi$ be a shortest path from $s$ to $t$ with all inner vertices
  in $V(P)$.  All inner vertices of $\pi$ are \emph{reflex}.
\end{lemma}

\begin{proof}
  Suppose $\pi$ has an inner vertex $v$ that is not reflex.
  Let $e_1, e_2 \in E(\pi)$ be the edges of $\pi$ and
  $f_1, f_2 \in E(P)$ the edges of $P$ incident on $v$.
  There exists $\eps > 0$ such that the $\eps$-ball $B = B(v, \eps)$ around
  $v$ intersects only $v$,  $e_1$, $e_2$, $f_1$, and $f$.
  Let $w_1$ and $w_2$ be the intersections of $\partial B$
  with $e_1$ and $e_2$. Since $v$ is not reflex, the segment
  $w_1w_2$ lies in $P$. As in the proof of Lemma~\ref{lem:polyVert},
  by shortcutting at $w_1w_2$ we can obtain a path from
  $s$ to $t$ that is strictly shorter than $\pi$, a contradiction,
  see Fig.~\ref{fig:polyInnerAng}(c).
\end{proof}

Next, we show that shortest paths with the same origin do not intersect
properly; see Fig.~\ref{fig:polyPropIntersect}.
\begin{figure}
  \centering
  \includegraphics{polyPropIntersect}
  \caption{(a) and (b): segments $e_1$ and $e_2$ intersect properly;
     (c) and (d): segments $e_1$ and $e_2$ do not intersect properly.}
  \label{fig:polyPropIntersect}
\end{figure}
\begin{lemma}\label{lem:noProperCrossing}
    Let $s, t_1, t_2 \in P$. Let $\pi_1$ be a shortest path in $P$ from
    $s$ to $t_1$, and let $\pi_2$ be a shortest path in $P$ from
    $s$ to $t_2$. Suppose that all inner vertices of $\pi_1$ and
    $\pi_2$ lie in $V(P)$, and that no edge of $\pi_1$ and $\pi_2$
    contains a vertex of $V(P)$. Then $\pi_1$ and $\pi_2$ do 
    not intersect properly,
    i.e., for any two edges $e_1$ of $\pi_1$ and $e_2$ of $\pi_2$, 
    we have either (i) $e_1 = e_2$; or  (ii) the edges $e_1$ and 
    $e_2$ are disjoint or share at most one endpoint.
\end{lemma}

\begin{proof}
  Suppose that the edges $e_1 \in E(\pi_1)$ and $e_2 \in E(\pi_2)$
  intersect properly. Let $x$ be the intersection point.
  Then $x$ cannot be a vertex of $P$, or else $e_1$ or $e_2$
  would contain a vertex of $P$. Thus, $x$ must lie in the interior of
  $P$. The paths $s \stackrel{\pi_1}{\longrightarrow} x$
  and $s \stackrel{\pi_2}{\longrightarrow} x$ must have the same
  length; otherwise we could shorten one of $\pi_1$ or $\pi_2$. 
  Thus, we can obtain a path from $s$ to $t_1$ of the same length
  by taking 
  $s \stackrel{\pi_2}{\longrightarrow} x \stackrel{\pi_1}{\longrightarrow} t_1$.
  However this path has $x$ as an inner vertex at which the adjacent 
  edges are not collinear. Thus, as in the proof of Lemma~\ref{lem:polyVert},
  we can obtain a strictly shorter path from $s$ to $t_1$, a contradiction.
\end{proof}

Using our results so far, we can prove that shortest paths in polygons
are unique.
\begin{lemma}\label{lem:uniquePath}
  The shortest path from $s$ to $t$ in $P$ is unique, up to subdivision of edges.
\end{lemma}

\begin{proof}
  Exercise. 
\end{proof}

\section{Computing Shortest Paths}

We now describe how to compute the shortest path from 
$s$ to $t$ in $P$.
Let $T$ be a triangulation of $P$, and let $D_s$ be the triangle
that contains $s$ and $D_t$ the triangle that contains $t$. 
We may assume that $D_s \neq D_t$, since otherwise the
shortest path is the line segment $st$.

The dual graph $T^*$ of $T$ is a tree (exercise).
Therefore, $T^*$ contains a unique path 
$D_s = D_1, D_2, \dots, D_k = D_t$
from $D_s$ to $D_t$.
For $i = 1, \dots, k-1$, let
$d_i$ be diagonal that is common to $D_i$ and $D_{i+1}$.
Furthermore, let $D_1' = \conv(s, d_1)$ and $D_k' = \conv(t, d_{k-1})$.
The \emph{sleeve} $S$ of $s$ and $t$ in $P$ is the polygon
$D_1' \cup D_k' \cup \bigcup_{i = 2}^{k-1} D_i$; see Fig.~\ref{fig:polySleeve}.
The shortest path from $s$ to $t$ lies completely in $S$, and
it crosses each diagonal $d_i$ exactly once.
Hence, all vertices of $\pi$ are vertices of $S$.

\begin{figure}
\centering
\includegraphics{polySleeve}
\caption{(a) A triangulation of $P$ and the triangles connecting $s$ and
$t$. The sleeve is shown in light gray; (b) the sleeve of $s$ and $t$, with
the corresponding sequence of triangles.}
\label{fig:polySleeve}
\end{figure}
The boundary of $S$ can be partitioned into two polygonal chains from $s$
to $t$: the \emph{left chain} (clockwise) and the \emph{right chain}
(counterclockwise). For each diagonal $d_i$, we denote the vertex of 
$d_i$ on the left chain by $l_i$, and the vertex on the right chain
by $r_i$. Now, the algorithm for computing the
shortest path from $s$ to $t$ proceeds iteratively: we successively 
find the shortest paths $\lambda_1,\lambda_2, \dots, \lambda_{k-1}$ from $s$ to
$l_1, l_2, \dots, l_{k-1}$ and $\rho_1,\rho_2, \dots, \rho_{k-1}$
from $s$ to $r_1, r_2, \dots, r_{k-1}$. The shortest paths $\lambda_1$
and $\rho_1$ are trivial to compute, and we will see that there is a
simple method to go from $\lambda_i$ and $\rho_i$ to
$\lambda_{i+1}$ and $\rho_{i+1}$. By Lemmas~\ref{lem:noProperCrossing}
and \ref{lem:uniquePath}, 
the paths $\lambda_i$ and $\rho_i$ share the same vertices until some
vertex $v$, after which they diverge into two noncrossing
branches. 

\begin{lemma}
Let $i \in \{1, \dots, k-1\}$, and consider
$\lambda_i$ and $\rho_i$. Let $v$ be the last
common vertex of $\lambda_i$ and $\rho_i$. Then,
(i) all inner vertices of $v \stackrel{\lambda_i}{\longrightarrow} l_i$ 
are on the left chain, and all inner vertices of 
$v \stackrel{\rho_i}{\longrightarrow} r_i$ are on the right chain;
(ii) $v \stackrel{\lambda_i}{\longrightarrow} l_i$ and
$v \stackrel{\rho_i}{\longrightarrow} r_i$ are concave inside the
sleeve; and  (iii) 
$s \stackrel{\lambda_i}{\longrightarrow} v = 
s \stackrel{\rho_i}{\longrightarrow} v$.
\end{lemma}

\begin{proof}
Exercise.
\end{proof}

We say that $\lambda_i$ and $\rho_i$ form a \emph{funnel}.
The path $s \stackrel{\lambda_i}{\longrightarrow} v$ is called the
\emph{tail} of the funnel: the vertex $v$ is the
\emph{apex} of the funnel; see Fig.~\ref{fig:polyFunnel}(a).
The shortest path algorithm iteratively computes the $i$-th funnel $F_i$,
for $i = 1, \dots, k-1$.
\begin{figure}
\centering
\includegraphics{polyFunnel}
\caption{(a) A funnel: $v$ is the apex; all vertices between
$v$ and $l_i$ lie on the left chain, all vertices between
$v$ and $r_i$ lie on the right chain; 
(b) The position of $r_{i+1}$ uniquely determines the
next-to-last vertex $w$ on $\rho_{i+1}$.}
\label{fig:polyFunnel}
\end{figure}
How does the funnel change as we proceed from $i$ to $i+1$? 
The diagonals $d_i$ and $d_{i+1}$ 
have one endpoint in common, so suppose that
$l_{i+1} = l_{i}$ and $\lambda_{i+1} = \lambda_i$
(the other case is symmetric).
We only need to find $\rho_{i+1}$,
given $F_i$.
Since we know the shortest paths from $s$ to all previous vertices
on the sleeve, it is enough to identify the 
next-to-last vertex $w$ of $\rho_{i+1}$.
By Lemma~\ref{lem:noProperCrossing}, the paths
$\lambda_{i+1}, \rho_i$, and $\rho_{i+1}$ do not intersect,
so $w$ must lie on $F_i$, on or after the apex. 
Finally, the inner angle of $\rho_{i+1}$ at $w$ must 
be reflex. This determines $w$ uniquely, see Fig.~\ref{fig:polyFunnel}(b).

\begin{lemma}\label{lem:advance}
The shortest path $\rho_{i+1}$ is obtained by taking
the last vertex $w$ on $\rho_{i}$ or $\lambda_i$ that makes
a reflex inner angle with $r_i$ and by extending 
the shortest path from $s$ over $w$ to $d_{i+1}^{r}$.
The vertex $w$ is either the apex of $F_i$,
or it comes after the apex.\qed
\end{lemma}

\section{Algorithm}

We can now state the shortest path algorithm.
First, we find the sleeve  $S$ for $P$,
$s$, and $t$, and we determine the diagonals
$d_1, \dots, d_{k-1}$.
The shortest paths $\lambda_i$ and $\rho_i$ are
represented as two doubly linked lists that
store bidirectional pointers to the
vertices on the paths. Furthermore, we maintain
a pointer $v$ to the apex of the current funnel.
We initialize $\lambda_1$ as $s \rightarrow l_1$ 
and $\rho_1$ as $s \rightarrow r_1$. The 
initial apex $v$ is $s$.

In the main loop, we iterate for 
$i = 1, \dots, k-2$. 
We take $z$ to be the endpoint of $d_{i+1}$ that
is not an endpoint $d_i$. If $z = r_{i+1}$, 
we walk backwards along
$\rho_i$ until we encounter either $v$ 
or the first vertex $w$ that 
is reflex with respect to $z$. If $w$ and
$z$ make a reflex vertex, we set
$\rho_{i+1}$ to $s \stackrel{\rho_i}{\longrightarrow} w \rightarrow z$
by changing the pointers at $w$.
Otherwise, we walk forward along $\lambda_i$ 
up to the first vertex
$w$ that can see $z$; see Fig.~\ref{fig:polyFunnel}(b). 
We then set $\rho_{i+1}$ to
$s \stackrel{\lambda_i}{\longrightarrow} w \rightarrow z$,
and we move the apex $v$ to $w$; see
Fig.~\ref{fig:polyAdvance}.
If $z$ is $l_{i+1}$, we proceed symmetrically.

Once $\lambda_{k-1}$ and $\rho_{k-1}$ are known, we 
perform one more update step to find the shortest 
path from $s$ to $t$.

\begin{figure}[ht]
\centering
\includegraphics[scale=0.8]{polyAdvance}
\caption{Advancing the funnel: (a) $w$ lies on the right chain;
(b) $w$ is the apex; or (c) $w$ lies on the left chain and the
apex moves forward.}
\label{fig:polyAdvance}
\end{figure}

\section{Analysis}

Correctness of the algorithm follows from Lemma~\ref{lem:advance}.
It remains to bound the running time. 
Using the polygon triangulation algorithm from class, we
need $O(n \log n)$ time to find the sleeve. If a triangulation
of $P$ is known, or if we use a more advanced triangulation
algorithm, the time reduces to $O(n)$.
Furthermore, it takes $O(1)$ steps to initialize the funnel.

Finally, we claim that the total time to update the funnel
is $O(n)$: in each iteration, the running time is proportional
to the number of vertices we traverse on $\lambda_i$ and $\rho_i$.
Every vertex we traverse, except the last one, is either deleted 
or moved behind the apex.  Once this happens, 
this vertex is never traversed again.
Thus, the amortized time per iteration is constant, and the
total time is linear.

\begin{theorem}
Given a simple polygon $P$ with $n$ vertices, and 
two points $s$ and $t$ in $P$, we can find the shortest 
path from $s$ to $t$ in $P$ in total time $O(n)$.
\end{theorem}
\end{document}