text:
\section{Introduction}\label{introSec}

The motivation for our work comes from
the generation of toolpaths for pocket machining.
Pocket machining is the process of cutting some specified pocket in
a piece of material -- in our case most likely a piece of metal --
using a milling machine.
We first describe the clean mathematical problem that we solve and afterwards
explain how it relates to pocket machining.

Consider a simply-connected closed subset of the plane and the
weakly simple, closed curve around its boundary which we traverse in
counter-clockwise direction. We say that the curve is convex where it
turns left and concave where it turns right.  We say it has {\em
  bounded convex curvature\/} if it turns left with curvature at most
$1$. There is no bound on the right-curvature, and we may even have
sharp concave corners.  We say that a set in the plane has bounded
convex curvature if all the connected components are simply-connected
and the weakly simple, closed curve around the boundary of each connected
component has bounded convex curvature.
Similarly, we say that a closed curve has \emph{bounded curvature in general}
if it turns to the left and to the right with curvature at most $1$.

\begin{wrapfigure}[9]{r}{0.15\textwidth}
\vspace{-20pt}
\input{composition.tex}
\caption{}
\label{compositionFig}
\end{wrapfigure}

A nice composition property of sets of bounded convex curvature is that if
we take two such sets $Q_1$ and $Q_2$, unite them, and fill out
any holes, then the resulting set, denoted $Q_1\uplusQ_2$,
has bounded convex curvature.
See Figure \ref{compositionFig}, where the boundary of
$Q_1\uplusQ_2$ is the thick curve.
This composition property does not hold if we demand that the curvature is
bounded in general.

The input to our problem is a simply-connected closed set of points $P$ in
the plane such that the boundary $\partial P$ is a curvilinear
polygon consisting of $n$ line segments and circular arcs of arbitrary
radii.
We present an algorithm that in $O(n\log n)$ time finds the unique maximum subset
$Q \subseteq P$ of bounded convex curvature, that is,
$Q$ contains any other $Q' \subseteqP$ of bounded convex curvature.
See Figure \ref{disconnectedFig} for an example.

We note that the uniqueness of a maximal subset $Q$ of bounded convex curvature
follows from the composition property; for if there was another $Q'\subseteq
P$ of bounded convex curvature that was not contained in $Q$,
then $Q\uplusQ'$ would also be contained in $P$ and
have bounded convex curvature, contradicting the maximality of $Q$.

The boundary of $Q$ will be a curvilinear polygon consisting of $O(n)$ line
segments and circular arcs. A very useful property of the boundary of
$Q$ is that all concave arcs and vertices are also on the boundary
of $P$. Indeed, it is easy to verify that if there is a concave arc
or vertex on the boundary of $Q$ which is not on the boundary of
$P$, then $Q$ is not maximal. A similar reasoning implies that if
the boundary of $P$ is a simple curve, then so is the boundary of $Q$.

\begin{wrapfigure}[9]{r}{0.35\textwidth}
\vspace{-20pt}
\input{newDisconnected.tex}
\caption{}
\label{disconnectedFig}
\end{wrapfigure}

We now describe different contexts in which this problem appears
naturally. The general problem is that we are given an area $S$ of the plane
whose boundary is represented as a curvilinear polygon.
There is a thin layer of material in $S$ close to the boundary
$\partial S$ of $S$. The goal is to remove that layer without removing anything from outside $S$. We are given a rough
tool, and we want to remove as much as possible of the thin layer, leaving as little as
possible for finer tools that are more expensive to use. The output is
a toolpath for the rough tool consisting of one or more curvilinear
polygons. The tool is a disk $\mathscr D$ of radius $r$, where $r$ is
bigger than the width of the layer we wish to remove.  The toolpath is
the path which the center of $\mathscr D$ is following and the material cut
away is the area swept by $\mathscr D$ as its center follows the toolpath.
The reason that we only have to handle a thin layer close to the boundary of $S$ is because the area farther from the boundary is removed beforehand by tools
that are less precise since they do not get close to the boundary.
Thus we may assume that the material at
all points at some distance $\delta\leq r$ from the boundary have been removed. Some of the points closer to the boundary may also have been removed, but this only makes it easier for our tool to move.
With this in mind, when the tool follows a weakly simple closed curve, we think of it as removing the interior of the curve plus every point at distance at most $r$ to the curve.

Let $P$ be the inwards offset of $S$ by $r$, that is, $P$ is the subset of $S$
of points with distance at least $r$ to the pocket boundary $\partial S$.
See Figure \ref{beforeAfterRounding}. $P$ is the set of all allowed
positions of the center of $\mathscr D$.
If we had complete control over the
tool, then we would be able to remove the material in all of $P$ and at
all points with distance at most $r$ from $P$ by letting the tool center traverse
the boundary $\partialP$. However, there are restrictions
on what tool paths we can follow, e.g., we cannot count on following a toolpath
with sharp corners in a precise way.

\begin{figure}%
\vspace{-20pt}
\centering
\includegraphics[scale=1]{toolpathFigs.pdf}
\caption{A pocket bounded by $\partial S$. To the left is shown
the boundary $\partialP$ of the inwards offset of $S$ by $r$.
To the right is shown the boundary $\partialQ$ of the maximum subset
with bounded
convex curvature of $P$.
The dotted arcs in
the corners show the boundary of the material in $S$
that cannot be removed by $\mathscr D$ using the two toolpaths.}%
\label{beforeAfterRounding}
\end{figure}

We are now ready to describe the first application where we
want to compute the maximum subset of bounded
convex curvature.
Assume that the tool can only follow a
path which has bounded curvature in general. Assume furthermore that
the tool can turn at least as sharply as its own
boundary, that is, $r\geq 1$.

\begin{wrapfigure}[11]{r}{0.35\textwidth}
\vspace{-20pt}
\centering
\includegraphics[scale=1]{heartFig.pdf}

\caption{}
\label{heartExFig}
\end{wrapfigure}

Using our algorithm for bounded convex curvature, we are able to identify the
maximum area that can be removed by the tool such that the toolpath
has bounded curvature in general. First we compute the above set $P$
which is the inwards offset of $S$ by $r$. The boundary $\partialP$
can be computed from the Voronoi diagram of $\partial S$
\cite{held1998voronoi}. Clearly the toolpath has to stay inside
$P$. We now note that every concave part of $\partial P$ has
curvature at most $1/r\leq 1$. Next we use our algorithm to find the
maximum subset $Q\subseteq P$ of bounded convex curvature, see
Figure \ref{beforeAfterRounding}. The area cut away as $\mathscr D$ follows
$\partialQ$ is the unique maximum subset
that can be cut out of $S$ using a tool with radius $r\geq 1$ and
such that the toolpath has bounded convex curvature. However, all concave arcs and
vertices on $\partialQ$ stem from $P$ which has concave curvature
at most $1/r\leq 1$.  It follows that using the toolpath $\partialQ$,
we cut out the maximum
subset of $S$ under the condition that the toolpath
has bounded curvature in general. This also
implies that we remove the maximum subset of the thin layer of material
close to the pocket boundary $\partial S$.

In the above example, the set $P$ had bounded concave curvature. In
particular, all concave arcs on $\partialP$ have radius at least $r$,
and for each concave arc $A$ on $\partial P$ of radius
$r$ and center $v$, there is an associated concave vertex $v$ of
$\partial S$. Let $a$ and $b$ be the first and last point on
$A$. When the tool follows $A$, the corner $v$ will be on the
tool boundary $\partial\mathscr D$, and the slightest imprecision will
blunt the corner $v$. A recommended alternative
\cite{park2003mitered} is that we substitute $A$ with two line
segments $aw$ and $wb$ tangential to $A$ at $a$ and $b$,
respectively, thus creating a sharp concave corner $w$ on the
toolpath, see Figure \ref{heartExFig}.  Using this technique, the
corner $v$ will be cut much sharper and more precise.  One can think of
various variations of this technique, since we can ``casually'' stop
and turn the tool at any point on its way to $w$ because the remaining
toolpath already ensures that all material will be cut away.  This
shows that we cannot in general assume that there is any bound on the
concave curvature of the input toolpath. We also note the asymmetry with
convex corners and arcs, where overshooting a convex corner implies an
illegal cut through the boundary of $S$.

We shall now provide a completely different explanation for the need
for bounded convex curvature. The point is that it is often preferable
for the surface quality of the resulting part that the tool moves with a constant
speed. Recall that the tool is only removing a thin layer
close to the pocket boundary. The width of this layer is typically a
deliberately chosen small fraction of the tool radius $r$.
When moving at constant speed, a convex
turn implies a higher engagement of the tool in the sense of the amount of
material removed per time unit.
In concave turns the engagement is only decreased.  A too high
engagement could break the tool, and therefore we must bound the
convex curvature of the tool path.

These and other
issues related to the machining of corners have been extensively studied in the
technical literature on pocket machining.
See for instance
the papers \cite{choy2003corner,han2015precise,
iwabe1994study,pateloup2004corner,zhao2007pocketing}.
There are several previous papers suggesting methods to get bounded
convex curvature, but none of them guarantees an optimal solution like
ours. One idea for how to handle convex corners is to replace each
of them by a convex circular arc as deep in the corner
as possible. This is suggested and studied
in the papers \cite{choy2003corner,iwabe1994study,pateloup2004corner}.
However, in all the papers it is assumed that every corner is formed by two
line segments which are
sufficiently long (relative to the angle between them) that a tangential
corner-rounding arc of sufficient size can be placed inside the wedge
they form.
As can be seen in Figure \ref{beforeAfterRounding}, this is not always the case,
and rounding a toolpath can require more complicated modifications.

\begin{wrapfigure}[8]{r}{0.47\textwidth}
\vspace{-10pt}
\includegraphics{bone.pdf}
\caption{}
\label{boneFig}
\end{wrapfigure}

One heuristic used
to obtain a non-trivial subset of bounded convex curvature is
the \emph{double offset method}, where we offset
$P$ inwards by $1$ and then offset the result outwards by
$1$ and use that as $Q$. This can be computed in $O(n\log n)$ time
using Voronoi diagrams \cite{yap1987ano}.  However, the method does
not in general result in the maximum subset of bounded convex curvature.
See for instance Figure \ref{boneFig}, where
$P$
has bounded convex curvature and all material in $S$ will be machined using $\partialP$
as the toolpath. $\partial S$ is the thick solid curve and
$\partialP$ is the thin solid curve.
The innermost dotted curves are the boundary of the
inwards offset of $P$ by $1$.
The area of $S$ between the thick dashed arcs will not be
machined if the double offset method is used.

We establish the mathematical foundation of
our work in Section \ref{mathFound}
by introducing a new generalization of the theorem of Pestov and Ionin.
In Section \ref{algoDescription} we describe an algorithm that computes the
maximum subset of bounded convex curvature of $P$.
In Section \ref{anImplementation} we describe how to implement
the algorithm so that it uses $O(n)$ space and runs in $O(n\log n)$ time.

\subsection{General notation and conventions}

If $M$ is a set of points in the plane, $\partial M$ denotes the boundary of $M$ and $\overline M$ denotes the
closure of $M$.
Let $\gamma$ be a simple curve and $x$ and $y$ two points on $\gamma$.
Then $\gamma[x,y]$ is the portion of $\gamma$ between $x$ and $y$ including
$x$ and $y$. Similarly, $\gamma(x,y)$, $\gamma[x,y)$,
and $\gamma(x,y]$ are used in the obvious way when none or one
of $x,y$ is included.
If $\gamma$ is a closed curve,
$\gamma[x,y]$ denotes the portion of $\gamma$
from $x$ to $y$ in the counterclockwise direction. As before,
round parenthesis can be used to exclude one or both endpoints.
If $\gamma$ is not closed, the order of $x$ and $y$ does not matter.
We say that a point $z\in\gamma$ is an \emph{inner point} of $\gamma$ if
$z$ is not an endpoint of $\gamma$.

\section{Mathematical foundation: The theorem of Pestov and Ionin}\label{mathFound}

An oriented, simple curve $\gamma$ is in the class $\mathcal L^+$ if $\gamma$ turns
to the left with curvature at most $1$, but
$\gamma$ is allowed to turn to the right arbitrarily sharply.
There can be corners on $\gamma$
where $\gamma$ is not differentiable, but in such corners $\gamma$
has to turn to the right.
These notions are defined rigorously below.
Note that a portion of a closed curve with bounded
convex curvature traversed in counterclockwise direction is a curve in
$\mathcal L^+$.

The correctness of the algorithm presented in this paper depends on the following
generalization of the Pestov-Ionin Theorem, see Figure \ref{mainThmFig}.

\begin{figure}
\centering
\includegraphics[scale=1]{PestovIoninFig.pdf}
\caption{Cases where Theorem \ref{mainThm} does and does not apply.}
\label{mainThmFig}
\end{figure}

\comm{
\begin{wrapfigure}[5]{r}{0.6\textwidth}
\centering
\vspace{-25pt}
\includegraphics[scale=1]{PestovIoninFig.pdf}
\caption{Cases where Theorem \ref{mainThm} does and does not apply.}
\label{mainThmFig}
\end{wrapfigure}
}

\begin{theorem}\label{mainThm}
Consider an open disk $D$ of arbitrary radius and a curve
$\gamma$ in $\mathcal L^+$ from $a$ to $b$ such that
$\gamma\cap \overline D=\{a,b\}$.
Let $R$ be the region bounded by $\partial D[b,a]$ and
$\gamma$. If $R$ contains $D$, then
$R$ contains an open unit disk $U$ such that there exists a point
$c\in\partial U\cap\gamma(a,b)$.
\end{theorem}

From the theorem, the following corollary easily follows.

\begin{corollary}\label{UCinL}
Every simple, closed curve $\gamma$ with bounded convex curvature
contains an open unit-disk in its interior.
\end{corollary}

The original theorem by Pestov and Ionin \cite{pestov1959largest} was
similar to Corollary \ref{UCinL}, but $\gamma$ was assumed to
have bounded curvature in general.
Howard and Treibergs \cite{howard1995reverse} proved Corollary \ref{UCinL}
for closed curves $\gamma$ with bounded convex curvature for a more restricted class of
curves.
Ahn et al.~\cite{ahn2012reachability} proved a theorem similar to Theorem
\ref{mainThm}, but assuming that $\gamma$ has bounded curvature in general.
Hence, the version of the theorem presented here
generalizes all previous versions known to the authors of the present paper.
The reader who is not interested in the formal definitions and
the proof of the theorem can jump directly to Section
\ref{algoDescription}.

\subsection{Definition of the class $\mathcal L^+$ and proof of Theorem \ref{mainThm}}

Let $\gamma: [0,L]\to \mathbb R^2$ be a simple, continuously differentiable curve parameterized by
arc length.
We sometimes use $\gamma$ as a short-hand notation for the set of points $\gamma([0,L])$ on $\gamma$.
We define the coordinate fuctions $\gamma_x$ and $\gamma_y$ of $\gamma$
such that $\gamma(s)=(\gamma_x(s),\gamma_y(s))$.
Let $\mathbf n(s)=\widehat{\gamma'}(s)=(-\gamma_y'(s),\gamma_x'(s))$ be the unit normal of $\gamma$ in $s$.

We define $\KKn^+$ to be the simple, continuously differentiable
curves $\gamma:[0,L]\to\mathbb R^2$ parameterized by arc length such that for every
$s\in [0,L)$ there exists a $H>0$ such that for all $h\in[0,H]$ we have
$\langle \gamma'(s+h)-\gamma'(s),\mathbf n(s)\rangle \leq h$, where
$\langle\cdot, \cdot\rangle$ is the dot-product. We denote the class of all such curves
as $\KKn^+$. Howard and Treibergs \cite{howard1995reverse} use a similar definition.
We first prove a theorem similar to Theorem \ref{mainThm}, but for curves in
$\KKn^+$ which is a subset of $\mathcal L^+$. In Section \ref{sharpCorners},
we prove the general result by showing how to handle curves with sharp corners.

\begin{exmp}
Consider a counterclockwise arc of radius $r>0$,
$\gamma(s)=(r\cos\frac sr,r\sin\frac sr)$.
We only need to consider
$s=0$ to check if $\gamma$ is in $\KKn^+$.
We get $\langle\gamma'(h)-\gamma'(0),\mathbf n(0)\rangle=\sin\frac hr$.
Since $\lim_{h\to 0}\frac{\sin\frac hr}{h/r}=1$,
$\gamma$ is in $\KKn^+$ if and only if $r\geq 1$.

On the other hand, if $\gamma(s)=(r\cos\frac sr,-r\sin\frac sr)$ is a clockwise arc,
we get $\langle\gamma'(h)-\gamma'(0),\mathbf n(0)\rangle=-\sin\frac hr<h$,
so $\gamma$ is in $\KKn^+$ for any $r$.
\end{exmp}

Whenever $\gamma$ is continuously differentiable and parameterized by arc length,
there exists a continuous function
$\vartheta: [0,L]\to \mathbb R$ such that
$$\gamma'(s)=(\cos \vartheta(s),\sin \vartheta(s))$$
and
$$\gamma(s)=
\gamma(0)+\left(\int_0^s \cos \vartheta(r)\, dr,\int_0^s \sin \vartheta(r)\, dr\right).$$
We denote $\vartheta$ as the \emph{tangent indicatrix} associated to $\gamma$.
When more curves are in play, we denote the tangent indicatrix of
$\gamma$ as $\vartheta_\gamma$.

If $p$ is a point and $S$ is a set of points,
$\textrm{dist}(p,S)=\inf_{s\in S} \|p-s\|$. We usually define distances to compact sets
$S$ so that there is a point $s\in S$ for which $\textrm{dist}(p,S)=\|p-s\|$.

\begin{lemma}\label{bigslope}
Let $s > 0$ and $f: [0,s]\to \mathbb R$ be a continuous function such that $f(0)=0$ and
$\vartheta(s)=(1+\varepsilon)\cdot s$
for $\varepsilon > 0$. Then there exists an $r\in[0,s)$ such that for all
$x\in [r, s]$ we have $f(x)\geq f(r)+(1+\varepsilon)(x-r)$.
\end{lemma}

\begin{proof}
Consider the function $g(x)=f(x)-(1+\varepsilon)\cdot x$.
Choose a global minimum $r$ of $g$. If $g$ is a non-negative
function, we can choose $r=0$. Therefore, $r<s$ in any case. For
$x\in[r,s]$, we now have
$f(x)-(1+\varepsilon)\cdot x\geq f(r)-(1+\varepsilon)\cdot r$ and hence
$f(x)\geq f(r)+(1+\varepsilon)(x-r)$.
\end{proof}

\begin{lemma}\label{slowvv}
Let $\gamma: [0,L]\to \mathbb R^2$ be a continuously differentiable curve parameterized by arc length and let
$\vartheta:[0,L]\to\mathbb R$ be the associated tangent indicatrix.
Then the following two conditions are equivalent:
\begin{enumerate}
\item $\gamma$ is in $\KKn^+$.
\item For all $p\in[0,L)$ and for all $q\in [p,L]$ we have $\vartheta(q)-\vartheta(p)\leq q-p$. \label{condTwo}
\end{enumerate}
\end{lemma}

\begin{proof}
Assume first that condition \ref{condTwo} holds. Without loss of generality, we may
assume that $\vartheta(0)=0$ and
prove that $\gamma$ is in $\KKn^+$ by verifying the curvature condition for $s=0$.
Choose $H\in(0,\pi/2]$ such that $\vartheta([0,H])\subseteq [-\pi/2,\pi/2]$. For every $h\in[0,H]$ we now have
$\langle \gamma'(h)-\gamma'(0),\mathbf n(0)\rangle =
\sin\vartheta(h)\leq h$, since $\sin x$ is increasing for $x\in[-\pi/2,\pi/2]$ and $\vartheta(h)\leq h$ for all
$h$. Therefore,
the curvature condition is satisfied.

Assume now that condition \ref{condTwo} does not hold, i.e., that
$\vartheta(q)-\vartheta(p)>q-p$ for some $q$ and $p$, $p\leq q$.
Lemma \ref{bigslope} gives that there exists an $r\in[p,q)$ such that
for all $x\in[r,q]$ we have $\vartheta(x)\geq \vartheta(r)+(1+\varepsilon)(x-r)$.
Assume without loss of generality that
$r=0$ and $\vartheta(0)=0$ so that $\vartheta(x)\geq (1+\varepsilon)\cdot x$ for all $x\in[0,q]$.
Then
$\langle \gamma'(x)-\gamma'(0),\mathbf n(0)\rangle=\sin\vartheta(x)>x$ when $x$ is small enough and the curvature condition is not satisfied.
\end{proof}

A \emph{wedge} is the intersection between two closed half-planes defined
by two non-parallel lines.
The \emph{tip} of the wedge is the intersection point of the two lines defining the
half-planes.

\begin{lemma}\label{localdisjoint}
Let $\gamma: [0,L]\to \mathbb R^2$ be a curve in $\KKn^+$ and let $D$ be an open unit disk with center
$\gamma(s)+\mathbf n(s)$ for some fixed $s\in[0,L]$.
Then $\gamma$ is disjoint from $D$ in a neighborhood around $\gamma(s)$,
i.e., there exists a $h>0$ such that $\gamma(I)\cap D=\emptyset$
for $I=[s-h,s+h]\cap [0,L]$.
\end{lemma}

\begin{proof}
We assume that $s<L$ and only show the existance of $h>0$ such that
$\gamma([s,s+h])\cap D=\emptyset$. The other case follows from symmetry.
Without loss of generality, assume that
$\gamma(0)=(0,-1)$, $\gamma'(0)=(1,0)$, $\vartheta(0)=0$, and $s=0$, so that
$D$ is the unit disk with center $(0,0)$. Choose $h\in(0,\pi/4]$ such that
$\vartheta([0,h])\subseteq [-\pi/4,\pi/4]$. Lemma \ref{slowvv} gives that $\vartheta(x)\leq x$, and since
$\cos x-\sin x$ is decreasing for $x\in[-\pi/4,\pi/4]$, we get for $x\in[0,h]$ that
$$\cos x-\sin x\leq \cos\vartheta(x)-\sin\vartheta(x).$$
By integrating over $x\in[0,s]$ for
$s\in[0,h]$, we get
$$\cos s+\sin s\leq \gamma_x(s)-\gamma_y(s).$$
Since $\sin x$ is increasing for $x\in[-\pi/4,\pi/4]$,
we also have
$$\gamma_y(s)=\gamma_y(0)+\int_0^s \sin\vartheta(x)\, dx\leq
-1+\int_0^s \sin x\, dx=-\cos s.$$
Therefore, for any $s\in[0,h]$, $\gamma(s)$ is in the area
$$A_s=\{(x,y)\mid y\leq x-\cos s-\sin s\enskip\textrm{and}\enskip y\leq-\cos s\}.$$
$A_s$ is the wedge of points between the two half-lines starting at $(\sin s,-\cos s)$ with directions
$(-1,-1)$ and $(1,0)$, respectively. Therefore,
$A_s$ and $D$ are clearly disjoint when $0\leq s\leq \pi/4$,
and hence $\gamma([0,h])$ is disjoint from $D$.
\end{proof}

In the remaining part of this section,
we consider an open disk $D$ of arbitrary radius $\delta$ and a curve
$\gamma:[0,L]\to\mathbb R^2$ in class $\KKn^+$ such that
$\gamma\cap \overline D=\{\gamma(0),\gamma(L)\}$.
The endpoints of $\gamma$ divide $\partial D$ into two arcs
$\partial D[\gamma(0),\gamma(L)]$ and
$\partial D[\gamma(L),\gamma(0)]$.
One of them is interior and one is exterior in the sense
that the interior is contained in the region bounded by the exterior and $\gamma$.
Let $R$ be the open region bounded by $\partial D[\gamma(L),\gamma(0)]$
and $\gamma$.
Assume that $\partial D[\gamma(0),\gamma(L)]\subset\overline R$
is interior.
Observe that $R$ is to the left of $\gamma$ and that $D\subset R$.

For the following lemma, it is actually not necessary that $\gamma\in\KKn^+$.

\begin{lemma}\label{notExtInner}
Let $g$ be an inner point on $\gamma$ and
let $U$ be the largest open disk contained in $R$ such that
$\partial U$ contains $g$. Then $\partial R\cap\partial U\subset \gamma$.
\end{lemma}

\begin{proof}
Assume for contradiction that $\partial U$ contains a point
$d\in\partial D(\gamma(L),\gamma(0))$.
This means that the radius of $U$ is at most $\delta$ and that
$\partial U$ is contained in $\overline D$. Therefore, $\partial U$ cannot
pass through the point $g$ for $g\notin\{\gamma(0),\gamma(L)\}$.
\end{proof}

Let $\overline\gamma$ be the closed curve obtained by adding the line segment from
$\gamma(L)$ to $\gamma(0)$ to $\gamma$. $\overline\gamma$ is simple since the added line
segment is in $\mathcal D$.
Define the \emph{tangent} of $\gamma$ with angle $\varphi$ as
the line $T_{\varphi}$ with normal vector $\mathbf m(\varphi)=(\cos \varphi,\sin\varphi)$ such that
$T_{\varphi}$ contains $\gamma(s')$ for
$s'=\textrm{argmax}_{s\in[0,L]} \langle \gamma(s), \mathbf m(\varphi)\rangle$.
$T_{\varphi}$ is a tangent of the convex hull of
$\overline\gamma$ which contains the extreme points in direction
$\mathbf m(\varphi)$.

Let $\mathcal H$ be the boundary of the convex hull of $\overline\gamma$.
Since $\overline\gamma$ is a simple, closed curve, $\mathcal H$ is as well.
The following Lemma is well-known.

\begin{lemma}\label{cyclicorder}
The cyclic order of the points on $\mathcal H$ is the same as on
$\overline\gamma$, that is, let $a,b,c\in\mathcal H\cap\overline\gamma$
and assume that $b\in\mathcal H(a,c)$. Then
$b\in\overline\gamma(a,c)$.
\end{lemma}

\begin{lemma}\label{noinner}
If $L<\pi$, there is no angle $\varphi$ and $a,b\in[0,L]$ such that
$\gamma(a)\in T_\varphi$, $\gamma(b)\in T_{\varphi+\pi}$, and $\gamma'(a)=-\gamma'(b)$.
In particular, there does not exist an angle $\varphi$ such that both $T_\varphi$ and
$T_{\varphi+\pi}$ contain an inner point of $\gamma$.
Furthermore, there exists an angle $\theta$ such that
$\gamma\cap T_\theta=\{\gamma(0)\}$ and
$\gamma\cap T_{\theta+\pi}=\{\gamma(L)\}$.
\end{lemma}

\begin{proof}
Assume that there is an angle $\varphi$
such that
$\gamma(a)\in T_\varphi$, $\gamma(b)\in T_{\varphi+\pi}$, and $\gamma'(a)=-\gamma'(b)$
and assume without loss of generality that $a<b$.
Let $\widehat{\mathbf m}(x)=(-\sin x,\cos x)$.
If $0<a$, we must have
$\gamma'(a)=\widehat{\mathbf m}(\varphi)$ and hence
$\gamma'(b)=\widehat{\mathbf m}(\varphi+\pi)$. The same holds when
$b<L$.
If $a=0$ and $b=L$, we must have
$\gamma'(0)\in\widehat{\mathbf m}([\varphi,\varphi+\pi))$
since otherwise the interior of $\overline\gamma$ is on wrong side of $T_\varphi$ in a neighborhood
around $\gamma(0)$.
Similarly $\gamma'(L)\in\widehat{\mathbf m}((\varphi,\varphi+\pi])$. Thus,
we must have
$\gamma'(0)=\widehat{\mathbf m}(\varphi)$ and
$\gamma'(L)=\widehat{\mathbf m}(\varphi+\pi)$.
We have seen that in any case,
$\gamma'(a)=\widehat{\mathbf m}(\varphi)$ and
$\gamma'(b)=\widehat{\mathbf m}(\varphi+\pi)$.

Construct the curve $\rho$ consisting of $\gamma([a,b])$, then a line segment
$\ell_0$ on $T_{\varphi+\pi}$
with direction $\gamma'(b)$ of length $L$, then a counterclockwise
semi-circle $\mathcal C$ tangential to $T_{\varphi}$ and $T_{\varphi+\pi}$,
and then a line segment $\ell_1$ on $T_\varphi$
to $\gamma(a)$.
We now observe that $\rho$ is simple. $\gamma([a,b])$ cannot cross
$\ell_0$ or $\ell_1$ due to Lemma \ref{cyclicorder} and not $\mathcal C$ since $\ell_0$ has length $L$. Furthermore, $\rho$ is continuously differentiable.

Let $\vartheta_\rho$ and $L_\rho$ be the tangent indicatrix associated to and length of $\rho$, respectively.
Hopf's Umlaufsatz gives that $\vartheta_\rho(L_\rho)-\vartheta_\rho(0)=2\pi$,
see for instance \cite[Thm. 11.1]{mccleary2012geometry}. We now have
$\vartheta_\rho(L_\rho)-\vartheta_\rho(b-a)=\pi$ since $\vartheta_\rho$ increases by $\pi$ along $\mathcal C$.
Hence $\vartheta_\gamma(b)-\vartheta_\gamma(a)=\vartheta_\rho(b-a)-\vartheta_\rho(0)=2\pi-(\vartheta_\rho(L_\rho)-\vartheta_\rho(b-a))=\pi$.
By Lemma \ref{slowvv}, either $b-a\geq \pi$ or $\gamma$ is not in $\KKn^+$, which is a contradiction.

If $T_\varphi$ contains an inner point $\gamma(t)$, then
$\gamma'(t)=\widehat{\mathbf m}(\varphi)$.
Therefore, $T_{\varphi+\pi}$ cannot contain an inner point, i.e.,
$\gamma\cap T_{\varphi+\pi}\subset \{\gamma(0),\gamma(L)\}$.
Hence, there exists an angle $\alpha$ such that
$\gamma\cap T_\alpha\subset\{\gamma(0),\gamma(L)\}$.
Assume without loss of generality that $\gamma(0)\in\gamma\cap T_\alpha$.
Now, let $\beta$ be the smallest angle larger than $\alpha$ such that
$T_\beta$ contains an inner point
of $\gamma$ or $\widehat{\mathbf m}(\beta)=\gamma'(0)$.
Then $\gamma(0)\in \gamma\cap T_{\beta}$ and
$\gamma\cap T_{\beta+\pi}=\{\gamma(L)\}$.
Thus, by choosing $\theta$ slightly smaller than $\beta$, where $\theta$ depends on $\gamma$,
we also have $\gamma\cap T_{\theta+\pi}=\{\gamma(L)\}$ while
$\gamma\cap T_{\theta}=\{\gamma(0)\}$.
\end{proof}

\begin{lemma}\label{baseRestrictions}
If $L<\pi$, then $\partial D[\gamma(0),\gamma(L)]$ spans an angle of less
than $\pi$, $\delta>1$, and $\gamma$ is contained in $\overline U$,
where $U$ is the open unit disk with
a center in the closed
half-plane to the left of the directed line from $\gamma(0)$ through $\gamma(L)$
such that $\gamma(0),\gamma(L)\in\partial U$.
\end{lemma}

\begin{proof}
If the interior arc of $\partial D$ spans an angle of $\pi$ or more,
it contains two antipodal points defining a diameter of
$D$. Assume without loss of generality that the diameter is horizontal.
Then, the tangents
$T_{0}$ and $T_{\pi}$ contain points on $\gamma$ with opposite vertical tangents,
contradicting Lemma \ref{noinner}.

To prove the two remaining statements,
we show that we can reduce the problem to the case
where $\delta=1$. Note that in that case, $D=U$.
Assume for contradiction that one of the remaining statements does
not hold.
In each case, $\gamma$ is not contained in $\overline U$.
We choose a maximal
interval $[p,q]\subseteq [0,L]$ such that
$\gamma([p,q])\cap\overline U=\{\gamma(p),\gamma(q)\}$.
Considering $U$ instead of $D$ and restricting $\gamma$ to the interval
$\gamma([p,q])$,
we now have a similar situation as described in the Lemma where
$\delta=1$ and $\gamma([p,q])$ is not contained in $U$.
Hence, let us in the following assume that $\delta=1$
and that $\gamma([0,L])$ is not a subset of $\overline D$.

Denote $\mathcal I=\partial D[\gamma(0),\gamma(L)]$.
Let $\theta$ be an angle such that $\gamma\cap T_\theta=\{\gamma(0)\}$
and $\gamma\cap T_{\theta+\pi}=\{\gamma(L)\}$.
The existence of $\theta$ is ensured by Lemma \ref{noinner}.

Now, imagine that we
slide $\mathcal I$ along the two tangents
$T_\theta$ and $T_{\theta+\pi}$
in direction $\widehat{\mathbf m}(\theta)$ until the last point of contact with $R$. Let $\mathcal I'$ be the translation of
$\mathcal I$ to this point and $\gamma(\sigma)$ the last point of contact,
which are well-defined since both $\gamma$ and $\mathcal I$ are compact.
$\gamma(\sigma)$ cannot be any of the end points of $\mathcal I'$ since the tangents
only contain end points of $\gamma$.
Hence, $\gamma(\sigma)$ is an inner point of $\mathcal I'$, and
$\mathcal I'$ and $\gamma$ share a tangent in $\gamma(\sigma)$.
It follows that $\mathcal I'$ is an arc on the boundary
of the open unit disk $A$
with center $\gamma(\sigma)+\mathbf n(\sigma)$.
$\gamma$ enters $A$ on a point on the arc from $\gamma(\sigma)$ to the end of $\mathcal I'$ since the end of $\mathcal I'$ is not on $\gamma$.
That contradicts Lemma \ref{localdisjoint}.
\end{proof}

\begin{theorem}\label{pi1}
The region $R$ contains an open unit disk $U$ such that $\gamma(s)\in\partial U$ for some
$s\in[\sigma,L-\sigma]$, where
$\sigma=\min\left\{\frac{\|\gamma(0)-\gamma(L)\|}{2},\frac{\pi}{2}\right\}$.
\end{theorem}

\begin{proof}
Inspired by Ahn et al.~\cite{ahn2012reachability},
we proceed by induction on $\lfloor L/\pi\rfloor$. For the base-case, assume
that $L<\pi$.

We see that for any $s\in (0,L)$, we can choose an open unit disk
$U\subset R$ such that $\gamma(s)\in\partial U$. Namely, assume that for some
$p\in(0,L)$ there is no such unit disk. Consider the largest open unit disk
$D'\subset R$ where $\gamma(p)\in\partial D'$. From Lemma \ref{notExtInner},
we know that $\partial D'$ contains a point $\gamma(q)\in\gamma([0,L])\setminus\{\gamma(p)\}$.
Lemma \ref{localdisjoint} gives that $\gamma$ is disjoint from $\overline{D'}$ in
a neighborhood around $p$ since the radius of $D'$ is less than $1$.
Therefore, we assume without loss of generality that $p<q$ and that $\gamma([p,q])\cap\overline{D'}=\{\gamma(p),\gamma(q)\}$.
But then $\gamma[p,q]$ is not in $\KKn^+$ by Lemma \ref{baseRestrictions}.

For the induction step,
assume that the theorem is true when $\lceil L/\pi\rceil\leq k-1$ and consider a curve
$\gamma$ with length $L$ such that $\lceil L/\pi\rceil=k$.
We first show the weaker statement that there is an open unit disk $U\subset R$
such that $\gamma(s)\in\partial U$ for some $s\notin\{0,L\}$.
This will be needed when showing that we can choose $s\in[\sigma,L-\sigma]$.
Let $p=L/2$ and let $D'$ be the largest open disk such that
$D'\subset R$ and $\gamma(p)\in\partial D'$.
If the radius $\delta'$ of $\partial D'$
is at least $1$, we are done. Otherwise, due to Lemma \ref{notExtInner},
$\partial D'$ contains a point
$\gamma(q)\in\gamma([0,L])\setminus\{\gamma(p)\}$.

Lemma \ref{localdisjoint} gives that $\gamma$ is disjoint from $\overline{D'}$ in an interval to each side
of $p$ since $\delta'<1$.
Therefore, we assume without loss of generality that $p<q$ and that $\gamma((p,q))\cap\overline{D'}=\emptyset$.
The curve $\gamma([p,q])$
has length at most $L/2$, so the induction hypothesis gives that the open region
$R'$ bounded by $\partial D'[\gamma(q),\gamma(p)]$ and $\gamma([p,q])$
contains an open unit disk $U$,
such that $\partial U$ contains $\gamma(s)$ from some $s\in(p,q)$. We note that $R'\subseteq R$ and $s\notin\{0,L\}$, as required.

To prove that we can choose $s$ in the interval $[\sigma,L-\sigma]$,
let $D_1$ be the largest open disk contained in $R$ such that $\partial D_1$ contains $\gamma(\sigma)$.
Assume $D_1$ has a radius smaller than $1$, since otherwise, we
are done.
By Lemma \ref{notExtInner}, there exists a point
$\gamma(p_1)\in\partial D_1\setminus\{\gamma(\sigma)\}$.
By Lemma \ref{baseRestrictions} we get that $p_1>\sigma$ since otherwise
$\gamma([0,\sigma])$ is not in $\KKn^+$.
If $p_1\leq L-\sigma$, we know from the above discussion that there
exists an open unit disk $U$ contained in the region bounded by
$\partial D_1[\gamma(p_1),\gamma(\sigma)]$ and
$\gamma([\sigma,p_1])$ such that $\partial U$ contains
a point $\gamma(s)\in\gamma((\sigma,p_1))$.
Hence also $s\in [\sigma,L-\sigma]$, as stated in the theorem.

If $p_1>L-\sigma$,
let $R_1$ be the region bounded by $D_1[\gamma(p_1),\gamma(\sigma)]$
and $\gamma([\sigma,p_1])$, and
let $D_2$ be the largest open disk contained in $R_1$
such that $\partial D_2$ contains $\gamma(L-\sigma)$.
Assume that $D_2$ has a radius of less than $1$, since otherwise we are done.
Lemma \ref{notExtInner} gives that there is a point
$\gamma(p_2)\in\partial D_2\cap\gamma([\sigma,p_1])\setminus \{\gamma(L-\sigma)\}$.
Lemma \ref{baseRestrictions} gives that $p_2<L-\sigma$ since otherwise
$\gamma([p_2,p_1])$ is not in $\KKn^+$. Hence,
$p_2\in [\sigma,L-\sigma)$, and from the above discussion
we know that
there is an open unit disk $U$ contained in the open region bounded by
$\partial D_2[\gamma(L-\sigma),\gamma(p_2)]$ and
$\gamma([p_2,L-\sigma])$ such that $\partial U$ contains a point
$\gamma(s)\in\gamma((p_2,L-\sigma))$. This proves the theorem.
\end{proof}

\subsubsection{A generalization to curves with sharp corners}\label{sharpCorners}

Let $\gamma:[0,L]\to\mathbb R^2$ be a curve and assume that
the backward tangent
$\gamma'_-(s)=\lim_{x\to s-}{\frac{\gamma(s)-\gamma(x)}{s-x}}$
is defined for all $s\in(0,L]$
and the forward tangent
$\gamma'_+(s)=\lim_{x\to s+}{\frac{\gamma(s)-\gamma(x)}{s-x}}$
is defined for all $s\in[0,L)$.
Furthermore, assume that
$\|\gamma'_-(s)\|$ and $\|\gamma'_+(s)\|$ is $1$ where they are defined.

We say that $\gamma(x)$ is a \emph{corner} if
$\gamma'_+(x)\neq\gamma'_-(x)$. For technical reasons, we also define
$\gamma(0)$ and $\gamma(L)$ to be corners and say that
$\gamma(x)$ is a \emph{proper} corner if
$x\notin\{0,L\}$.
Let $X$ be the set of all corners. We do not assume $X$ to be finite,
but it follows from the Denjoy--Young--Saks Theorem
\cite[p. 63, Thm. 4.2]{bruckner1978differentiation} that $X$ is countable.
\comm{
http://math.stackexchange.com/questions/128806/real-valued-function-of-one-variable-which-is-continuous-on-a-b-and-semi-diffe
}

We define $\mathbf n_+(x)=\widehat{\gamma'_+}(x)$ for every $x\in [0,L)$ and
$\mathbf n_-(x)=\widehat{\gamma'_-}(x)$ for every $x\in(0,L]$.
At a point $\gamma(x)$ which is not a corner, the unit-normal
$\mathbf n(x)=\mathbf n_+(x)=\mathbf n_-(x)$ is defined
as for differentiable curves. At other points, the unit-normal is undefined.

At a proper corner $\gamma(x)$, $\gamma$ either makes a
turn to the left or to the right.
If $\langle\widehat{\gamma'_-}(x),\gamma'_+(x)\rangle<0$, it is a left-turn
and if $\langle\widehat{\gamma'_-}(x),\gamma'_+(x)\rangle>0$ it is a right-turn.
If $\langle\widehat{\gamma'_-}(x),\gamma'_+(x)\rangle=0$, we
have $\gamma'_-(x)=-\gamma'_+(x)$.
To decide to which side $\gamma$ turns in this case,
we consider for each $n\in\mathbb N$ a circle
$\mathcal C_n$ with center $\gamma(x)$ and a radius so small that it intersects
both $\gamma([x-1/n,x])$ in a point $y_n$
and $\gamma([x,x+1/n])$ in a point $z_n$.
Since $\gamma'_-(s)$ and
$\gamma'_+(s)$ are well defined, the size of the
angle of the arc on $\mathcal C_n$
from $y_n$ counterclockwise to $z_n$ converges to either
$0$ or $2\pi$,
in which case $\gamma$ makes a right- or a left-turn
at $\gamma(x)$, respectively.

For each corner $\gamma(x)\in X$ where $x<L$, we define
$L_x=(x,\inf_{x<y,\gamma(y)\in X} y)$, where
$L_x$ is possibly empty. Note that $\gamma$ is differentiable on each interval
$L_x$. We say that $\gamma$ has
\emph{bounded left-curvature}
and write $\gamma\in\mathcal L^+$ if each
proper corner is a right-turn and $\gamma(\overline{L_x})\in\KKn^+$ for every
interval $L_x$.
Since $X$ is countable, $\gamma'$ is defined and continuous almost everywhere.
Therefore $\| \gamma'(y)\|=1$ almost everywhere.
Hence $\int_0^\ell \| \gamma'(y)\| dy=\ell$, so it makes
sense to say that $\gamma$ is parameterized by arc length.
It also holds that the shortest curve in $\mathcal L^+$ between two points follows
the line segment between the points, for instance,
the proof outlined in \cite[Exercise 1.2]{bonahon2009low} generalizes to our case.
The class $\KKn^+$ is clearly a proper subset of $\mathcal L^+$.

We are now ready to prove Theorem \ref{mainThm} as stated in Section \ref{introSec}.

\begin{proof}[Proof of Theorem \ref{mainThm}]
We prove that Theorem \ref{pi1} also holds when $\gamma\in\mathcal L^+$
instead of $\gamma\in\KKn^+$.
We construct a sequence of curves $\gamma_1,\gamma_2,\ldots$ in $\KKn^+$
with lengths $L_1,L_2,\ldots$, such that
$\gamma_n(0)=\gamma(0)$ and $\gamma_n(L_n)=\gamma(L)$
for all $n$.
The sequence converges to $\gamma$ in such a way that
Theorem \ref{pi1} applied to each curve $\gamma_n$ implies
the existence of a unit disk in $R$ as wanted.
Informally, we may describe $\gamma_n$ as the result of rounding
the proper corners of $\gamma$ with circular arcs of radii less than $1/2n$.

Each curve $\gamma_n$ is itself the limit of a sequence
$\gamma_{n,0},\gamma_{n,1},\ldots$ of curves in $\mathcal L^+$, such that
$\gamma_{n,0}=\gamma$ and $\gamma_{n,m+1}$ is the result
of rounding at least one corner of $\gamma_{n,m}$.
The endpoints of $\gamma_{n,m}$ are $\gamma(0)$ and $\gamma(L)$.

We define $\gamma_{n,0}=\gamma$ and $C_0=\emptyset$.
$C_m$ consists of the circular arcs on
$\gamma_{n,m}$ we have added to round the corners of $\gamma$.
Let $x_1,x_2,\ldots$ be an enumeration
of the parameters such that $\gamma(x_1),\gamma(x_2),\ldots$ are all
the proper corners of $\gamma$. Assume that we have already
defined the curve $\gamma_{n,m}$.
We now show how $\gamma_{n,m+1}$ is defined.

Choose the smallest $k$ such that $\gamma(x_k)$ is also a corner of
$\gamma_{n,m}$ and define $x$ such that
$\gamma(x_k)=\gamma_{n,m}(x)$.
Let $W$ we a wedge with tip $\gamma_{n,m}(x)$ such that
$\gamma_{n,m}$ is contained in $W$ in an interval before and after $x$.
Such a wedge exists since the forward and backward tangents of $\gamma_{n,m}$
are well-defined in $x$.
Let $w>0$ be a number so small
that the intersection between $\gamma_{n,m}$
and any open disk with center $\gamma_{n,m}(x)$ and
radius at most $w$ is an interval of $\gamma_{n,m}$ contained in $W$.
Then, let
$$r=\min\left\{
1/n,
w,
\textrm{dist}(\gamma_{n,m}(x),C_m),
\|\gamma_{n,m}(x)-\gamma(0)\|,\|\gamma_{n,m}(x)-\gamma(L)\|\right\}.$$
We assume inductively that $\textrm{dist}(\gamma_{n,m}(x),C_m)>0$ and hence $r>0$.
Let $\mathcal A$ be the open disk with center $x$ and radius $r$, and let
$\gamma_{n,m}([a,b])$ be the interval
$\overline{\mathcal A}\cap \gamma_{n,m}$,
where clearly $x\in[a,b]$.
The interval $\gamma_{n,m}([a,x])$ divides $W\cap \overline{\mathcal A}$ into two pieces,
and since $\gamma_{n,m}$ makes a right-turn at $\gamma_{n,m}(x)$,
$\gamma_{n,m}([x,b])$ is contained
in the piece to the right of $\gamma_{n,m}([a,x])$.

Let $\mathcal B$ be the open disk with center $\gamma_{n,m}(x)$ and radius $r/2$
and let $\partial\mathcal B'$ be the arc $\partial\mathcal B\cap W$.
The intersection points between $\partial\mathcal B'$ and $\gamma_{n,m}$
divide $\partial\mathcal B'$ into smaller arcs.
Consider the last intersection point
$\gamma_{n,m}(c)$ between $\gamma_{n,m}([a,x])$ and $\partial\mathcal B'$
following $\partial\mathcal B'$ in counterclockwise direction.
The arc $\partial\mathcal B''$
on $\partial\mathcal B'$ beginning at $\gamma_{n,m}(c)$ must end at a point $\gamma_{n,m}(d)$ on $\gamma_{n,m}([x,b])$, since otherwise, $\gamma_{n,m}$
cannot leave $\mathcal B$ after $\gamma_{n,m}(x)$.

For each point $p\in\partial\mathcal B''$,
we consider the largest open disk $\mathcal C_p$
with center $p$ disjoint from $\gamma_{n,m}$. In the following, we show that
for each $p\in\partial\mathcal B''$, we have
$\mathcal C_p\subset\mathcal A$ and that
$\gamma_{n,m}(x)\notin\partial\mathcal C_p$:
Let $\mathcal D$ be the largest open disk with center $p$
contained in $W$ and let $S$ be the region
bounded by $\gamma_{n,m}([a,b])$ and the arc on $\partial\mathcal A$ from
$\gamma_{n,m}(a)$
counterclockwise to $\gamma_{n,m}(b)$. Then
$\mathcal C_p\subset S\subset W$, so
$\mathcal C_p\subset \mathcal D$.
But $\partial\mathcal D$ does not contain
$\gamma_{n,m}(x)$ since $\gamma_{n,m}(x)$ is the tip of the wedge $W$.
Hence the radius of $\mathcal C_p$ is less than $r/2$ for all $p\in\partial\mathcal B''$.

When $p$ is close to $\gamma_{n,m}(c)$,
$\partial\mathcal C_p$ contains a point on $\gamma_{n,m}([a,x))$
while when $p$ is close to $\gamma_{n,m}(d)$, $\partial\mathcal C_p$ contains a point
on $\gamma((x,b])$. Therefore, there must be a point $P\in\partial\mathcal B''$
such that $\mathcal C_P$ contains a point
$\gamma_{n,m}(e)\in\gamma_{n,m}([a,x))$ and
a point on $\gamma_{n,m}(f)\in\gamma_{n,m}((x,b])$.

The interior of $S$, and hence $\mathcal C_P$,
is to the right of $\gamma_{n,m}([a,b])$ since
$\gamma_{n,m}(x)$ is a right-turn.
Therefore, since all corners on $\gamma_{n,m}$ are right-turns,
$\gamma_{n,m}(e)$ and $\gamma_{n,m}(f)$ cannot be corners,
so $\gamma_{n,m}$ is differentiable in $e$ and $f$, and
$\partial\mathcal C_P$ and $\gamma_{n,m}$ have the same tangents there.
We now define $\gamma_{n,m+1}$ as the curve identical to $\gamma_{n,m}$,
but where $\gamma_{n,m+1}$ follows the arc $\partial\mathcal C_P'$ on
$\partial\mathcal C_P$ from $\gamma_{n,m}(e)$ clockwise to
$\gamma_{n,m}(f)$ instead of the interval $\gamma_{n,m}([e,f])$.
We note that $\partial\mathcal C'_P$ is disjoint
from all the arcs in $C_m$ and
define $C_{m+1}=C_m\cup\partial\mathcal C_P'$. We also see that
$\textrm{dist}(\gamma_{n,m+1}(y),C_{m+1})>0$
for every remaining corner $\gamma_{n,m+1}(y)$ on $\gamma_{n,m+1}$.

We now define $\gamma_n$ as $\bigcap_{m=0}^\infty \gamma_{n,m}$,
i.e., $\gamma_n$ consists of all the points on $\gamma$ which are never substituted by
an arc and all the arcs $\bigcup_{m=1}^\infty C_m$.
It now follows from the construction that $\gamma_n\in\KKn^+$,
since each point on $\gamma_n$
is either a point on a clockwise circular arc or a point on $\gamma$ which is not a corner.

We note that the Hausdorff distance between $\gamma$ and $\gamma_n$ converges
to $0$, i.e.,
that the maximum distance from a point on $\gamma$ to the closest point
on $\gamma_n$ converges to $0$ as $n\to\infty$ and likewise for
the maximum distance from a point on $\gamma_n$
to the closest point on $\gamma$.

By Theorem \ref{pi1}, there exists a unit disk $U_n$ in the region
$R_n$ bounded by $D$ and $\gamma_n$ for each $n$, such that
$U_n$ touches $\gamma_n$ in an inner point $\gamma_n(s_n)$, where
$s_n\in[\sigma,L_n-\sigma]$,
where
$\sigma=\min\left\{\frac{\|\gamma(0)-\gamma(L)\|}{2},\frac{\pi}{2}\right\}$.
Hence, there exists an accumulation point $c$ among the sequence of the centers of
the disks $U_1,U_2,\ldots$. Let $U$ be the open unit disk with center $c$.
Since the Hausdorff distance between $\gamma$ and
$\gamma_n$ converges to $0$, $U$ is contained in $R$.
It remains to be proven that $\gamma(s)\in\partial U$ for some
$s\in[\sigma,L-\sigma]$.

We call a point on $\gamma_n$ a \emph{fixed point} if the point also
exists on $\gamma$. We note that the distance along $\gamma_n$
from an arbitrary point on
$\gamma_n$ to the closest fixed point in each direction
is less than $\pi/n$, since the point which are not fixed appear on circular arcs
of lengths less than $\pi/n$.
Furthermore, we see that every arc $\mathcal C_P'$ is not longer than the interval
$\gamma_{n,m}([e,f])$ that it substitutes:
It is well-known that $\gamma([e,f])$ is at least as long as any convex
polygonal chain from $e$ to $f$ contained in the area bounded by
$\gamma[(e,f)]$ and the line segment from $\gamma(e)$ to $\gamma(f)$
\cite{rohnert1986shortest}. The arc $\mathcal C_P'$ is the limit of a converging
sequence
of such polygonal chains and is hence also not longer than $\gamma_{n,m}([e,f])$.
Therefore, for each fixed point $\gamma_n(v)=\gamma(w)$, we have
$v<w$ and $L_n-v<L-w$.

Let $(a_n)$
be a subsequence of the positive integers $(n)$ such
that the center of $U_{a_n}$ converges to $c$.
The sequence $(\gamma_{a_n}(s_{a_n}))$
has an accumulation point $\gamma(s)$.
Let $(b_n)$ be a subsequence of $(a_n)$ such that
$\gamma_{b_n}(s_{b_n})$ converges to $\gamma(s)$.
The sequence $(s_{b_n})$ has an accumulation point $\chi$.
Let $(c_n)$ be a subsequence of $(b_n)$ such that
$s_{c_n}$ converges to $\chi$.
We choose a sequence
$(\chi_n)$ such that (i) $\chi_n\leq s_{c_n}$, (ii) $\chi_n$ converges to $\chi$, and
(iii) $(\gamma_{c_n}(\chi_n))$ is a sequence of fixed points.
As mentioned above, we have $\chi_n\leq s$
for each $n$ since $\gamma(\chi_n)$ is a fixed point. We thus have
$$\sigma\leq\lim_{n\to\infty}s_{c_n}=\chi=\lim_{n\to\infty}\chi_n\leq s.$$

Similarly, the sequence $(L_n-s_{b_n})$ has an accumulation point
$\psi$, and we choose a subsequence $(d_n)$ of $(b_n)$ such that
$L_n-s_{d_n}$ converges to $\psi$ and a sequence
$(\psi_n)$ such that (i) $\psi_n\geq s_{d_n}$, (ii) $L_n-\psi_n$ converges to $\psi$,
and (iii) $(\gamma_{d_n}(\psi_n))$ is a sequence of fixed points.
We then have
$$\sigma\leq\lim_{n\to\infty} L_n-s_{d_n}=\psi=\lim_{n\to\infty} L_n-\psi_n\leq L-s.$$
\end{proof}

\subsubsection{Closed curves with bounded convex curvature}

We say that a closed, simple curve
$\gamma$ has \emph{bounded convex curvature}
if every closed, connected, proper subset of
$\gamma$ can be parameterized as a curve $\tilde \gamma$
in $\mathcal L^+$ following the counterclockwise direction of $\gamma$.

\begin{proof}[Proof of Corollary \ref{UCinL}]
Consider a maximal open disk $D$ in the interior of $\gamma$ in the sense that
no other open disk in the interior of $\gamma$ contains $D$.
Assume that $D$ has radius less than $1$.
Clearly, $\partial D$ contains at least two points $a,b\in\gamma$. Since
$D$ has radius less than $1$, $\gamma$ must be different from $\partial D$.
Therefore,
we can choose $a$ and $b$ such that $\gamma[a,b]\cap\overline D=\{a,b\}$.
Now, Theorem \ref{mainThm} implies that the curve defined by
$\partial D[b,a]$ and $\gamma[a,b]$ contains an open unit-disk in its interior.
\end{proof}

\section{Algorithm}\label{algoDescription}

\subsection{Preliminaries}

We assume that a simply-connected region $P_1$
in the plane is given such
that the boundary $\partialP_1$ consists of a finite number of line segments
and circular arcs of arbitrary radii. For ease of presentation, we assume that
$\partialP_1$ is a simple curvilinear polygon, but our algorithm works as long
as $\partialP_1$ is weakly simple. We can therefore without loss of generality
assume that $P_1$ is an open set.
We set $P\getsP_1$
and our algorithm keeps removing parts of $P$
while maintaining the invariant that
$\overline{P}$ contains every subset of
$\overline{P_1}$ of bounded convex curvature.
In the end, $\overline{P}$ itself has bounded convex curvature and it follows
that $\overline{P}$ is the unique maximum subset of $\overline{P_1}$
of bounded convex curvature.

The region $P$ is always a collection of disjoint, open, simply-connected sets
each of which is bounded by a simple curvilinear polygon.
$P$ is represented by its boundary
$\partial P$, which is a collection
of disjoint, closed, simple curves where no curve is contained
in the interior of another. The input $P_1$ is defined by one such curve.
The open region enclosed by each curve is one connected component of $P$.
$\partial P$ is represented as a set of points known as the \emph{vertices}
of $\partialP$ and a set of line segments and circular arcs known as the \emph{arcs}
of $\partialP$.
We think of line segments as circular arcs with infinite radius and therefore
in most cases use the word \emph{arcs} for both circular arcs and line segments.
Depending on the context, we may consider a vertex as a point or a set
containing a single point.
An \emph{object} of $\partialP$ is a vertex or an arc.
We use the convention that an arc includes its endpoints.
Every two arcs of $\partialP$ are disjoint except possibly at the endpoints, and
for each vertex there are two arcs having an endpoint at that vertex.
This way, the arcs form the closed curves bounding $P$.
We always use $n$ to denote the number of vertices of the input $\partialP_1$.

The boundary of each connected
component of $P$ is oriented in counterclockwise direction
and we say that a point moving on $\partial P$
is moving \emph{forward} (resp.~\emph{backward})
if it is following (resp.~not following) the orientation of the boundary.
Similarly, we orient every arc following
the orientation of the boundary of the component containing it.
We denote the endpoints of an arc $A$ as $s(A)$ and $t(A)$,
so that a point moving forward along $A$ moves from $s(A)$
to $t(A)$.
An arc which turns to the left when traversed in forward direction
is called a \emph{convex arc}. A \emph{concave arc} is defined analogously.
Line segments are regarded as both concave and convex arcs
at the same time.
A vertex $v$ is \emph{convex} if the interior angle of $\partialP$ at $v$ is strictly less
than $\pi$. If the angle is strictly more than $\pi$, $v$ is \emph{concave}.

Let $A$ be an arc of $\partialP$ and $a\in A$ a point on $A$. Then
$\mathbf n_A(a)$ is the unit-normal of $A$ at $a$ which points to the left
relative to the orientation of $A$.
We say that two arcs $A$ and $B$ are \emph{tangential} if
$t(A)=s(B)$ and
$\mathbf n_{A}(t(A))=\mathbf n_{B}(s(B))$.
Note that $A$ and $B$ are tangential if and only if
the vertex $t(A)$ is neither convex nor concave.

\subsection{High-level description of the algorithm}

A high-level description of the algorithm is given as Algorithm \ref{roundAlg}.
The basic format is to maintain a stack $\Sigma$ of pointers to objects of $\partialP$
causing the convex curvature condition on $\partial P$ to be violated.
An object $\sigma\in\Sigma$ can be a convex vertex,
a convex arc of radius less than $1$, or a special \emph{cut arc}
of radius $1$, where one or both of the endpoints might be convex vertices.
In each iteration of the loop at line \ref{loop},
we test if the object $\sigma$ on the top of $\Sigma$ is still on $\partial P$
(it might have been removed in another iteration) and if so, we
eliminate it by removing from $P$ a subset
$\mathcal V\subseteq P$.
The object $\sigma$ appears on the boundary $\partial \mathcal V$ and not on
the boundary of $P\setminus \mathcal V$.
By \emph{performing a cut} or simply a \emph{cut},
we mean the process of removing
$\mathcal V$ from $P$. It is important to choose $\mathcal V$ such that
$\mathcal V\capQ=\emptyset$ for every set $Q\subset\overline{P_1}$
of bounded convex curvature.
Theorem \ref{mainThm} will be used to prove this.

It is possible that a cut splits $P$ into more components.
The algorithm will then keep working on each component separately.
A cut can introduce new unit-radius cut arcs on
$\partial P$, the endpoints of which can be convex vertices.
Therefore, these new cut arcs are added to $\Sigma$ so that the
new convex vertices are eventually removed.
The algorithm terminates when $\Sigma$ is empty, which means that $P$
has bounded convex curvature.

\begin{algorithm}[h]
\LinesNumbered
\DontPrintSemicolon
\SetArgSty{}
\SetKwInput{Input}{Input}
\SetKwInput{Output}{Output}
\SetKw{Report}{report}
\SetKwIF{If}{ElseIf}{Else}{if}{}{else if}{else}{end if}
\SetKwFor{Foreach}{for each}{}{end for}
\SetKwFor{While}{while}{}{end while}
Add all convex arcs of $\partial P$ with a radius less than $1$ to $\Sigma$.\;
Add all convex vertices of $\partial P$ to $\Sigma$.\;
\While {$\Sigma\neq\emptyset$} {\label{loop}
  Let $\sigma$ be the topmost element on $\Sigma$ and remove $\sigma$ from $\Sigma$.\;
  \If {$\sigma\subset \partial P$ and $\sigma$ is not a perfect cut arc} {
    Cut away $\mathcal V$ from $P$ and let $\mathcal C_{j}$, $j=1,\ldots,t$,
    be the new cut arcs after the cut.\;
    Add each new cut arc $\mathcal C_{j}$ to $\Sigma$.\;
  }
}
\Return {$P$}
\caption{$\ttt{SubsetOfBoundedConvexCurvature}(P)$}
\label{roundAlg}
\end{algorithm}

Let $P_i$ be the set $P$ in the beginning of iteration
$i=1,2,\ldots$ of the loop at line \ref{loop} in Algorithm \ref{roundAlg}.
We shall prove that the algorithm terminates after $k=O(n)$ iterations. Hence
we have
$$P_1\supseteqP_2\supseteq\cdots\supseteqP_k.$$
The challenge is to define $\mathcal V$ in each iteration
so that $k=O(n)$, $P\getsP\setminus\mathcal V$ can be computed efficiently, and
$\mathcal V\capQ=\emptyset$ for every set $Q\subset\overline{P_1}$ of bounded convex curvature.

\subsection{Specifying a cut using an arc $\mathcal C$}

Let $\sigma$ be an object from $\Sigma$
that is to be eliminated in a certain iteration of Algorithm
\ref{roundAlg}, and let $K$ be the connected component of $P$ such that
$\sigma\subset\partial K$.
If we conclude that $K$ does not contain any non-empty set of
bounded convex curvature,
we set $\mathcal V=K$, so that all of the component $K$ is removed from
$P$.
Otherwise, we specify $\mathcal V$ using a circular arc $\mathcal C$
of unit radius.
See Figure \ref{cutFig}, where $\mathcal C$ is grey and $\mathcal V$ is the area enclosed by the
thick closed curve.
Assume for now that we have defined $\mathcal C$.
Let $s(\mathcal C)$ and $t(\mathcal C)$ be the points where $\mathcal C$ starts
and ends in counterclockwise direction, respectively.
The endpoints are included in $\mathcal C$ and
are points on $\partial K$. They will be defined so that
$\sigma\subseteq\partialK[s(\mathcal C),t(\mathcal C)]$.
It will follow from the definition of $\mathcal C$ that there will be at most two vertices on $\partialK(s(\mathcal C),t(\mathcal C))$.
For efficiency, the algorithm may choose
an arc $\mathcal C$ that intersects $\partialK(s(\mathcal C),t(\mathcal C))$.

\begin{wrapfigure}[11]{r}{0.25\textwidth}
\vspace{-20pt}
\input{newCutEx.tex}
\caption{}
\label{cutFig}
\end{wrapfigure}

The arc $\mathcal C$ divides $K$ into open regions $R_1,\ldots,R_r$, which are
the connected components of $K\setminus\mathcal C$.
Assume without loss of generality that among all these regions, exactly the regions
$R_1,\ldots,R_s$, $s\leq r$, contain a part of
$\partialK(s(\mathcal C),t(\mathcal C))$ on their boundary.
We note that $s = 1$ if $\mathcal C$ does not intersect
$\partialK(s(\mathcal C), t(\mathcal C))$,
as is the case in Figure \ref{cutFig}.
Define $\mathcal V$ as the union $\bigcup_{i=1}^s K\cap \overline{R_i}$.
Then $K \setminus\mathcal V$ is open and hence so is our new
$P\gets P \setminus \mathcal V$.
The arc $\mathcal C$ will be carefully chosen so that
$\mathcal V\capQ=\emptyset$ for every set $Q\subset\overline{P_1}$
of bounded convex curvature.

\begin{lemma}\label{VVConnected}
$\mathcal V$ is connected and for each $i=1,2,\ldots$, the boundary $\partialK$
of each connected component $K$ of $P_i$ is a simple curvilinear polygon.
\end{lemma}

\begin{proof
Let two points $p,q\in\mathcal V$ be given. We can connect $p$ to $q$ by a
curve contained in $\mathcal V$ by walking along $\partialK(s(\mathcal C),t(\mathcal C))$.
Hence, $\mathcal V$ is connected.

Assume that every component of $P_i$ has a boundary which is a simple curve
and assume that the same is not true for the connected
component $K$ of $P_{i+1}$.
Let $\mathcal C$ be the arc specifying the cut that be made in $P_i$ to
obtain $P_{i+1}$.
There must be an arc $\mathcal C[a,b]$ on
$\partialK$ and a point $x\in\mathcal C(a,b)$ such that
$x\in\partialK(b,a)$.
But that implies that $K$ is not connected, which is a contradiction.
\end{proof}

Consider the case where we remove a proper subset $\mathcal V$
from a connected component $K$ of $P_i$ to obtain $P_{i+1}$.
One or more arcs $\mathcal C_1,\ldots,\mathcal C_t$ of $\partialP_{i+1}$ are subsets
of $\mathcal C$ and not arcs of $\partialP_i$.
We denote the arcs $\mathcal C_{1},\ldots,\mathcal C_{t}$ as
\emph{new cut arcs} of $\partialP_{i+1}$.
An arc of $\partialP_{i+1}$ which is a subset of a new
cut arc of $\partialP_j$, $j\leq i$, is not a new cut arc of $\partialP_{i+1}$.
An arc of $\partialP_{i+1}$ is a \emph{cut arc} if it is
the subset of a new cut arc of $\partialP_j$ for some $j\leq i+1$.
We say that a cut arc $\mathcal C$ of $\partialP$ is \emph{perfect}
if none of the endpoints of $\mathcal C$ are convex vertices.

\begin{lemma}\label{cutArcCCW}
Every cut arc of $\partialP$ is convex.
\end{lemma}

\begin{proof
We show that if the statement is true for $P_i$, then it is also true for
$P_{i+1}$.
Let $\mathcal C$ be the arc specifying a cut to be performed in $P_i$.
Assume that $\mathcal V$ is a subset of the connected component $K$
in $P_i$.
We proceed by induction on the number $r$ of
connected components $R_1,\ldots,R_r$ of $K\setminus\mathcal C$. If
$r=1$, the statement is trivial, since $\mathcal V=R_1=K$.

Consider the case $r=2$.
Assume that $\mathcal V=K\cap\overline R_1$ is removed
from $K$ and that $R_2$ remains, since otherwise there is nothing to show.
$R_2$ is bounded by some interval
$\partialK[a,b]$ and a subset $\mathcal C'$ of $\mathcal C$ with endpoints
$a$ and $b$. The points must appear in the order $s(\mathcal C),t(\mathcal C),a,b$ along
$\partialK$, since otherwise $R_2$ is removed.
Assume for contradiction that $\mathcal C'$ is a clockwise arc on
$\partial R_2$.
That means that the points appear in the order $s(\mathcal C),a,b,t(\mathcal C)$
along $\mathcal C$. Furthermore, since $r=1$,
$\mathcal C[s(\mathcal C),a]$ and $\mathcal C[b,t(\mathcal C)]$ are disjoint from
$K$, which means that $\partialK[b,a]$ does not
cross $\mathcal C$ from one side to the other.
There exists a point $a'\in\partialK[t(\mathcal C),a]$ which is not
on $\mathcal C$ since otherwise $b\in\partialK[t(\mathcal C),a]$,
contradicting that $\partialK$ is simple.
Let $s'(\mathcal C)$ be the first point on $\mathcal C[s(\mathcal C),a]$ we meet
when traveling along $\partialK$ from $b$. Let $b'$ be the last point on
$\mathcal C[a,t(\mathcal C)]$ we meet when traveling along $\partialK$ from
$b$ to $s'(\mathcal C)$.
Clearly, $b'\neq a$ and $b'\neqt(\mathcal C)$ since $\partialK$ is simple.
By construction,
$\partialK[b',s'(\mathcal C)]$ and $\mathcal C[s'(\mathcal C),b']$ form a simple
closed curve $J$. Orient $J$ so that $\mathcal C[s'(\mathcal C),b']$ is a counterclockwise
arc when traversing $J$ in forward direction. When walking from $a$ to $a'$ along
$\partialP[a',a]$, we leave $J$ to its left side.
When walking from $b'$ to $t(\mathcal C)$, we leave $J$ to its right side. Hence
$J$ separates $t(\mathcal C)$ from $a'$. Therefore,
$\partialK[t(\mathcal C),a']$ crosses $J$, which is a contradiction.

Assume now $r\geq 3$ and that the statement is true for smaller values of $r$.
Since $P$ is simply connected, the regions
$R_1,\ldots,R_r$ induce a tree $T$ such that two regions $R_j$ and $R_k$ are connected
if there is an arc $\mathcal C(x,y)\subset\partial R_j\cap\partial R_k$ for $x\neq y$.
Let $R_j$ and $R_k$ be two leafs in $T$.
Let $K_j=K\setminus \overline{R_j}$ and $K_k=K\setminus \overline{R_k}$.
$K_j$ and $K_k$ are both subdivided into $r-1$ regions by
$\mathcal C$, and
let $K_j'$ and $K_k'$ be the result of performing the cut specified by $\mathcal C$ in
$K_j$ and $K_k$, respectively.
Note that $R_j$ and $R_k$ are not neighbors in $T$ since $r\geq 3$
and hence both of the
unique neighbors in $T$ of $R_j$ and $R_k$ are also regions
in both $K_j\setminus\mathcal C$ and $K_k\setminus\mathcal C$.
Therefore, every new cut arc in $P_{i+1}$ is a new cut arc in either $K_j'$ or
$K_k'$. Hence, the induction hypothesis gives that
every cut arc of $\partialP_{i+1}$ is convex.
\end{proof}

\subsection{The bisector curve $\xi$}\label{bisectorXi}

\begin{wrapfigure}[12]{r}{0.22\textwidth}
\vspace{-20pt}
\centering
\input{xi2.tex}
\caption{}
\label{xiFig}
\end{wrapfigure}

A specific type of bisector
curve, illustrated in Figure \ref{xiFig},
turns out to be useful when describing
how to define the arc $\mathcal C$ specifying a cut and
when proving the correctness of our algorithm.
The curve is somewhat related to the medial axis of $\partialP$.
Before introducing the curve, we need
the concept of an \emph{osculating circle}.

Let $A$ be an arc of $\partialP$.
A circle $C$ \emph{osculates} $A$ at $a\in A$ if
the interior of $C$ is disjoint from $A$, $C$ and $A$ have the
point $a$ in common, and the center $x$ of $C$ is a point
$a+\mathbf n_A(a)\cdot c$ where $c\geq 0$. Recall that $\mathbf n_A(a)$ is the
unit-normal to $A$ in $a$ pointing to the left.
If $c=0$, $C$ is a single point.
Note that $a$ is the point on $A$ closest to $x$. A special case happens
when $A$ is an arc on $C$, in which case $A$ is a convex arc and
$C$ osculates $A$ at every point on $A$.

\begin{observation}\label{oscSmallRadius}
Let $A$ be an arc of $\partialP$ and $x$ an arbitrary point.
There exists at most one circle $C$
with center $x$ that osculates $A$. If such a circle $C$ exists,
the radius of $C$ is the distance to the closest point $a$ on $A$ from $x$
and $C$ osculates $A$ in $a$.
If $A$ is a convex arc, then the radius of $C$ is at most the radius of $A$.
\end{observation}

We denote the bisector curve as $\xi=\xi(A_0,A_1,x_0)$.
$A_0$ and $A_1$ are arcs of $\partialP$ and
$x_0$ is the point where $\xi$ begins.
$\xi$ consists of
at most three intervals to be defined below, each of which is part of a
conic section.
Depending on $x_0$, $\xi$ might start in the second or
third interval. From the context where $\xi$ is used, it will be clear
in which interval $\xi$ starts.

Often, but not always, $A_0$ and $A_1$ are neighboring arcs and
$x_0$ is their common endpoint, i.e.,
$x_0=t(A_0)=s(A_1)$. In this case,
$x_0$ will be a convex vertex of
$\partial P$ (as in Figure \ref{xiFig}) or
$A_0$ and $A_1$ are tangential. If
$A_0$ and $A_1$ are tangential,
one of $A_0$ and $A_1$ will be a cut arc.

For each point $x\in\xi$, we are going to define a circle $C_x$ and points
$\Pi_0(x)\in A_0\cap C_x$ and $\Pi_1(x)\in A_1\cap C_x$.
The circle $C_x$ has its center at $x$.
The functions $\Pi_0$ and $\Pi_1$ are the \emph{projections}
associated to $\xi$ and $C_x$ is the \emph{clearance circle} associated to
$\xi$ at $x$.

Interval \biDef 1 consists of points $x$ such that
$C_x$ osculates both $A_0$ and $A_1$
at points $\Pi_0(x)$ and $\Pi_1(x)$, respectively.
Interval \biDef 2 consists of points $x$
where $s(A_0)=\Pi_0(x)$ and $C_x$ osculates $A_{1}$
at a point $\Pi_{1}(x)$ or $t(A_1)=\Pi_1(x)$ and $C_x$ osculates
$A_0$ at a point $\Pi_0(x)$.
Interval \biDef 3 consists of points $x$ such that
$s(A_0)=\Pi_0(x)$ and $t(A_1)=\Pi_1(x)$.

Assume that $x_0$ is contained in interval \biDef 1.
In the following, we think
of $x$ as a point that traverses $\xi$ from $x_0$.

\textbf{Interval }\biDef 1\textbf{:}
$\xi$ consists of the points $x$ such that there is a circle $C_x$
with center $x$ that osculates
$A_0$ and $A_1$ at points $\Pi_0(x)$ and $\Pi_1(x)$, respectively.
Hence, this interval consists of points $x$ on $\xi$ such that the distance to the closest
points on $A_0$ and $A_1$ is the same.
In the general case,
as $x$ traverses $\xi$, $\Pi_0(x)$ moves continuously
backward and $\Pi_1(x)$ moves continuously forward.
We eventually reach a point $x_1$ where $C_{x_1}$
contains $s(A_0)$ or $t(A_1)$, and $\xi$ continues with the
interval defined in \biDef 2.
A special case occurs if $t(A_0)=s(A_1)$ and $A_0$ and $A_1$ are tangential. Then $x$ moves in the direction
$\mathbf n_{A_0}(t(A_0))$
until $x$ is the center $x_1$ of $A_0$ or $A_1$.
This happens since one of the arcs
is a cut arc. Until $x$ reaches $x_1$, the projections are constant,
$\Pi_0(x)=\Pi_1(x)=t(A_0)$. If $x_1$ is the center of $A_0$,
we define $\Pi_0(x_1)=s(A_0)$. Similarly, if
$x_1$ is the center of $A_1$, we define $\Pi_1(x_1)=t(A_1)$.

\textbf{Interval }\biDef 2\textbf{:}
$\xi$ has reached a point $x_1$ such that $C_{x_1}$
contains $s(A_0)$ or $t(A_1)$.
If $s(A_0)=t(A_1)$, $\xi$ stops here.
Otherwise, if $C_{x_1}$
contains both $s(A_0)$ and $t(A_1)$, interval \biDef 2
is degenerate, $x_2=x_1$,
and $\xi$ continues with the interval described in \biDef 3.
Otherwise, assume without loss of generality that $C_x$
contains $s(A_0)$ and osculates $A_1$.
From here, $\xi$ consists of points $x$ such that there is a circle $C_x$
with center $x$
that contains $s(A_0)=\Pi_0(x)$ and osculates $A_1$ at a point $\Pi_1(x)$.
When $x$ moves along $\xi$, $\Pi_1(x)$ moves continuously forward.
At some point, we reach a point $x_2$ where $C_{x_2}$
contains $s(A_0)$ and $t(A_1)$,
and $\xi$ continues with the interval defined in \biDef 3.

\textbf{Interval }\biDef 3\textbf{:}
At the last point $x_2$ of interval \biDef 2, $C_{x_2}$
contains both of the points $s(A_0)$ and $t(A_1)$.
Now, $\xi$ consists of the points $x$ such that there is a circle $C_x$
with center $x$ containing both $\Pi_0(x)=s(A_0)$ and
$\Pi_1(x)=t(A_1)$, i.e., $\xi$ follows a half-line.
We define the direction of the half-line to be
the counterclockwise rotation by an angle of $\pi/2$ of the vector
$t(A_1)-s(A_0)$.

When defining the arc $\mathcal C$ that specifies the cut we want to perform,
we are often searching for the first point $x_3$ on $\xi$ where $C_{x_3}$
has radius $1$. We shall then define $\mathcal C=C_{x_3}[\Pi_0(x_3),\Pi_1(x_3)]$.
Yap \cite{yap1987ano} showed that
each of the intervals \biDef 1--\biDef 3 is a part of a conic section.
Using elementary geometry
we can decide for each interval in $O(1)$ time if it contains a point $x_3$
such that $C_{x_3}$ has radius $1$.

\begin{wrapfigure}[7]{r}{0.55\textwidth}
\vspace{-20pt}
\includegraphics[scale=1]{bone2.pdf}
\caption{}
\label{bone2fig}
\end{wrapfigure}

Note that when $x_0=t(A_0)=s(A_1)$ and
$x_0$ is a convex vertex of $\partialP$, then
a portion of $\xi$ beginning at $x_0$ is a subset of the medial axis of
$\partialP$. However, $x_3$ (as defined above) need not be on the medial
axis and can even be outside $P$, also when $\mathcal C=C_{x_3}[\Pi_0(x_3),\Pi_1(x_3)]$
becomes a perfect cut arc.
See Figure \ref{bone2fig} for an example.

\begin{observation}\label{allOsculates}
If $A_k$ is a convex arc, $k=0,1$,
and $x_0=t(A_0)=s(A_1)$, then for each
$a\in A_k$, there exists $x\in\xi$ such that $C_x$ osculates $A_k$ at $a$,
and by Observation \ref{oscSmallRadius},
the radius of $C_x$ is at most the radius of $A_k$.
\end{observation}

\subsection{Defining the arc $\mathcal C$ specifying a cut}\label{cutDef}

The objects in $\Sigma$ are either \cutDef a
convex arcs of $\partialP_1$
with a radius less than $1$, \cutDef b
convex vertices of $\partialP_1$, or
\cutDef c
cut arcs. Below, we describe how to define $\mathcal C$ when the object $\sigma$
picked by Algorithm \ref{roundAlg} is of each of these types.

\textbf{Case }\cutDef a\textbf{:}
$\sigma$ is a convex arc with radius less than $1$.
Consider the curve $\xi=\xi(\sigma,\sigma,x_0)$, where $x_0$ is the center of $\sigma$,
which begins in interval \biDef 3.
Choose the first point $x_3\in\xi$ such that the associated clearance circle
$C_{x_3}$ has radius $1$ and define
$\mathcal C=C_{x_3}[\Pi_0(x_3),\Pi_1(x_3)]=C_{x_3}[s(\sigma),t(\sigma)]$.
Said in another way,
we define $\mathcal C$ to be the unit-radius arc counterclockwise
from $s(\sigma)$ to $t(\sigma)$ which spans an angle of less than $\pi$.

\textbf{Case }\cutDef b\textbf{:}
$\sigma$ is a convex vertex of $\partial P$.
Let $A_0$ be the arc of $\partial P$ before $\sigma$ and $A_1$ the arc after
$\sigma$. Consider the curve $\xi=\xi(A_0,A_1,x_0)$, where $x_0=\sigma$.
Find the first point $x_3\in\xi$ where
$C_{x_3}$ has a radius of $1$. If such a point does not exist, we are in the case
where $s(A_0)=t(A_1)$, and
we let $\mathcal V$ be the complete component $K$ of $P$ where $\sigma$
appears on the boundary
(in this case, the boundary of $K$ only has two arcs, $A_0$ and $A_1$).
Otherwise, we define $\mathcal C=C_{x_3}[\Pi_0(x_3),\Pi_1(x_3)]$.

\begin{wrapfigure}[10]{r}{0.17\textwidth}
\vspace{-35pt}
\input{chooseC.tex}
\caption{
\label{chooseCFig}
\end{wrapfigure}

\textbf{Case }\cutDef c\textbf{:}
$\sigma$ is a cut arc $B$.
We assume that one of the endpoints of $B$ is a convex vertex, since otherwise
$B$ is perfect and hence ignored by the algorithm.
If one of the endpoints, say $s(B)$, is a concave vertex,
then $t(B)$ is a convex vertex, and we do as if $\sigma=t(B)$ as described in
case \cutDef b.
We now assume that none of the endpoints of $B$ are concave vertices.
See Figure \ref{chooseCFig}.
Let $A_0$ and $A_1$ be the arcs preceding and
succeeding $B$ on $\partial P$, respectively.
Let $\xi_0=\xi(A_0,B,s(B))$ and $\xi_1=\xi(B,A_1,t(B))$.
For each $b\in B$, follow the ray starting at $b$ with direction $\mathbf n_B(b)$
and define $d_k(b)$ to be the distance from $b$ to the first intersection point with
$\xi_k$, $k=0,1$.
Since
$d_0(s(B))=0<d_1(s(B))$ and $d_1(t(B))=0<d_0(t(B))$,
the continuity of $\xi_k$ implies there must be
an intersection point
$x_0$ between $\xi_0$ and $\xi_1$.
By Observation \ref{allOsculates}, we know that the distance from $x_0$ to
$B$ is at most $1$.
We now consider the curve $\xi=\xi(A_0,A_1,x_0)$ with associated
projections $\Pi_0,\Pi_1$, and clearance circle $C_x$.
The clearance circle $C_{x_0}$ of $\xi$ at $x_0$ is the same as for $\xi_0$ and
$\xi_1$. If $C_{x_0}$ osculates $A_0$ and $A_1$, $\xi$ begins in
interval \biDef 1. If $C_{x_0}$ osculates one of $A_0,A_1$ and
contains an endpoint of the other, $\xi$ begins in interval \biDef 2.
Otherwise, $C_{x_0}$ contains $s(A_0)$ and $t(A_1)$, and
$\xi$ begins in interval \biDef 3.
We find the first point $x_3\in\xi$ where
$C_{x_3}$ has radius $1$.
If such a point does not exist, we are in the case
where $s(A_0)=t(A_1)$, and
we let $\mathcal V$ be the complete component $K$ of $P$ where $\sigma$
appears on the boundary. Otherwise,
we define $\mathcal C=C_{x_3}[\Pi_0(x_3),\Pi_1(x_3)]$.

One may object to the algorithm that since a connected component of $P$
can split into more components by a cut, the arcs on $\Sigma$ are not
necessarily well-defined, since subsets of the arc originally added to $\Sigma$
can be on the boundary of many
different connected components of $P$.
However, since the arcs are convex arcs of radius
at most $1$, the following lemma shows that it is not a problem.
The proof will be given in Section \ref{sepCritProof}.

\begin{lemma}\label{sepCrit}
Let $A$ be an arc of $\partialP_1$ which is a convex arc
of any radius
or a concave arc with radius at least $1$. For any $i\geq 1$,
there exists at most one connected component $K$ of $P_i$ such that
(a subset of) $A$ is an arc of $\partialK$.
\end{lemma}

\subsection{Proof of correctness of Algorithm \ref{roundAlg}}\label{correctness}

In this section, we prove that the set $\mathcal V$ to be cut away from $P$
is disjoint from every subset of $\overline{P_1}$ of bounded convex curvature.
The proof is by contradiction. The idea is that if there is a subset of
$\overline{P_1}$ of bounded convex curvature
that overlaps $\mathcal V$, then Theorem \ref{mainThm} gives the existence
of a unit disk in $\mathcal V$ which cannot be there. In general,
$\mathcal V$ can have a complicated shape and is not easy directly to reason about.
Therefore, we describe a superset of $\mathcal V$ consisting of \emph{simplices},
which are sufficiently simple that the argument goes through.

A \emph{simplex} $S$ is a closed region and has a boundary $\partial S$
which is a closed, simple curve consisting of two, three, or four circular arcs.
One of the arcs
$D$ on the boundary is the \emph{door}. The door $D$
has a radius of at most
$1$ and is clockwise when $\partialS$ is traversed
in counterclockwise order. We denote the following as the \emph{simplex condition},
which every simplex is required to satisfy:
Let $U$ be the closed disk such that
$\partial U$ contains the door $D$. Then
$U\cup S$ does not contain any unit-disk unless $U$ has radius $1$, in which
case $U$ is the only unit-disk contained in $U\cup S$.

Consider a curve $\xi=(A_0,A_1,x_0)$ with associated projections
$\Pi_0$, $\Pi_1$ and associated clearance circles $C_x$.
For $x_1,x_2\in\xi$, where
$x_1$ appear before $x_2$ on $\xi$, the \emph{simplex candidate}
associated to the pair $(x_1,x_2)$ is the curve consisting of
$A_0[\Pi_0(x_2),\Pi_0(x_1)]$,
$C_{x_1}[\Pi_0(x_1),\Pi_1(x_1)]$,
$A_1[\Pi_1(x_1),\Pi_1(x_2)]$,
and $C_{x_2}[\Pi_0(x_2),\Pi_1(x_2)]$.
The following lemma explains the connection between simplices and simplex candidates.

\begin{lemma}\label{simplexLemma}
Let $x_1$ and $x_2$ belong to the same interval of $\xi$ such that
$x_1$ appear before $x_2$. If there is no
$x\in\xi[x_1,x_2)$ for which the clearance circle $C_x$ has a radius of $1$ or more,
then the simplex candidate associated to $(x_1,x_2)$
is the boundary of a simplex $S$ with door $C_{x_2}[\Pi_0(x_2),\Pi_1(x_2)]$.
\end{lemma}

\begin{proof}
We prove the lemma when both $x_1$ and $x_2$ are in interval \biDef 1.
The other cases follow from similar arguments.
Since $x_1$ and $x_2$ are in interval \biDef 1, both of the circles
$C_{x_1}$ and $C_{x_2}$ osculate $A_0$ and $A_1$.
Assume that we are not in the case where $A_0$ and $A_1$ are tangential,
since in that case, the simplex candidate is the boundary of a degenerate simplex
and the statement trivial.
In the general case,
$C_{x_1}$ and $C_{x_2}$ have exactly one point in common with both
$A_0$ and $A_1$. Therefore, to check that the simplex candidate is simple,
we only need to see that $C_{x_1}[\Pi_0(x_1),\Pi_1(x_1)]$ and
$C_{x_2}[\Pi_0(x_2),\Pi_1(x_2)]$ do not intersect.
If they did, $C_{x_2}[\Pi_0(x_2),\Pi_1(x_2)]$ would cross
$C_{x_1}[\Pi_0(x_1),\Pi_1(x_1)$ at some point
$a\in C_{x_1}[\Pi_0(x_1),\Pi_1(x_1)$. Since $\Pi_1(x_2)$ is after
$\Pi_1(x_1)$ on $\partialP$, $C_{x_2}[\Pi_0(x_2),\Pi_1(x_2)]$
would have to cross $C_{x_1}[\Pi_0(x_1),\Pi_1(x_1)$ again at some point
$b$.
But then $C_{x_2}[b,a]$ is contained in the interior of $C_{x_1}$ and can hence not
reach a point $\Pi_1(x_2)\in A_1$.

Let $S$ be the closed region bounded by the simplex candidate.
We need to check that $S$ satisfies the simplex condition.
Let $U$ be the open disk inside $C_{x_2}$.
Assume for contradiction that there is another open
unit-disk $D$ in $S\cup U$. We now move $D$ such that the distance
from the center of $D$ to $x_2$ increases
until $D$ reaches the boundary of $S\cup U$. That must happen
at an inner point of
$A_0[\Pi_0(x_2),\Pi_0(x_1)]$ (resp.~$A_1[\Pi_1(x_1),\Pi_1(x_2)]$)
since we move $D$ away from $U$ and
$C_{x_1}$ has radius less than $1$.
We then ``roll'' $D$ forward on
$A_0$ (resp.~backward on $A_1$) until it would not be contained in $S\cup U$
if rolled any further. At this time, it must osculate both $A_0$ and $A_1$
at points in $A_0(\Pi_0(x_2),\Pi_0(x_1))$ and $A_1(\Pi_1(x_1),\Pi_1(x_2))$,
respectively. But then the center of $D$ is in $\xi(x_1,x_2)$ and $D$ has radius
$1$, contradicting the assumption.
\end{proof}

We say that the simplex $S$ from Lemma \ref{simplexLemma} is the simplex \emph{associated} to the pair $(x_1,x_2)$. In the following we specify a set
$\mathfrak S$ of simplices using simplex candidates. The set
$\mathfrak S$ will be used to prove the optimality of
the cut performed by our algorithm when some object $\sigma$ is handled.

If $\sigma$ is a convex arc of radius less than $1$, $\mathfrak S$ consists of
one simplex $S$,
which is the simplex associated to the pair $(x_0,x_3)$
as defined in point \cutDef a in Section \ref{cutDef}.
Put in another way, $S$ is
bounded by the two arcs $\sigma$ and $\mathcal C$, the latter being the door.

If $\sigma$ is a vertex, consider the curve $\xi$ defined in point \cutDef b
in Section \ref{cutDef}.
We make one simplex for each of the intervals
\biDef 1--\biDef 3 of $\xi$.
We only describe the situation where the center $x_3$
of $\mathcal C$ is in interval \biDef 3, since this is the most general case.
Let $x_1$ and $x_2$ be the points on $\xi$ at the end of interval \biDef 1 and
\biDef 2, respectively.
We now make one simplex associated to each of the pairs
$(x_0,x_1)$, $(x_1,x_2)$, and $(x_2,x_3)$.

If $\sigma$ is a cut arc $B$,
let $A_0$, $A_1$, $\xi_0$, $\xi_1$, $\xi$, $x_0$, $x_3$, $C_x$, $\Pi_0$,
and $\Pi_1$ be as defined in point \cutDef c in
Section \ref{cutDef}.
Let $\Pi_0^{(k)}$, $\Pi_1^{(k)}$, and $C^{(k)}$ be the
projections and clearance circle associated to $\xi_k$, $k=0,1$.
The circle $C_{x_0}$ is osculating $B$ at a point $q$.
Note that $C_{x_0}^{(0)}=C_{x_0}^{(1)}=C_{x_0}$,
$\Pi_0^{(0)}(x_0)=\Pi_0(x_0)$, $\Pi_1^{(0)}(x_0)=\Pi_0^{(1)}(x_0)=q$,
and $\Pi_1^{(1)}(x_0)=\Pi_1(x_0)$.

$x_0$ must be in interval \biDef 1 or \biDef 2 of
both $\xi_0$ and $\xi_1$, since interval \biDef 3 consists of points
of points $y$ where the circle $C_y^{(k)}$ does not osculate $B$.
If $x_0$ is in interval \biDef 1 of $\xi_0$, we use one simplex associated to
the pair $(s(B),x_0)$.
If $x_0$ is in interval \biDef 2, let $x_1^{(0)}$ be the end of interval \biDef 1.
We use simplices associated to the pairs
$(s(B),x_1^{(0)})$ and $(x_1^{(0)},x_0)$.
Note that in any case, we make a simplex with the door
$C_{x_0}[\Pi_0(x_0),q]$.
In a similar way, we make one or two simplices for pairs of points on $\xi_1$, where
one of them has the door
$C_{x_0}[q,\Pi_1(x_0)]$.

In the most general situation where $x_0$ is in interval \biDef 1,
let $x_1$ and $x_2$ be the points on $\xi$ where interval \biDef 1 and
\biDef 2 ends, respectively.
We now make one simplex associated to each of the pairs
$(x_0,x_1)$, $(x_1,x_2)$, and $(x_2,x_3)$.

The following is clear from the construction.

\begin{observation}\label{simplicesObservation}
For every point $p\in\partialP[s(\mathcal C),t(\mathcal C)]$, there exists a simplex
$S\in\mathfrak S$ such that $p\in\partialS$.
Furthermore, every point of $\partial\mathcal S$ is either on
$\partialP[s(\mathcal C),t(\mathcal C)]$ or on $\mathcal C$, where
$\mathcal S=\bigcup_{S\in\mathfrak S} S$.
\end{observation}

\begin{lemma}\label{simplexTree}
There exists
a set $\mathfrak S$ of at most five simplices such that if
$\mathcal S=\bigcup_{S\in\mathfrak S} S$,
then $\mathcal V\subset \mathcal S$ and
$\partial \mathcal S\subseteq
\partial P[s(\mathcal C),t(\mathcal C)]\cup \mathcal C$.
There is a tree $\mathfrak T$ with the nodes being
$\mathfrak S$ with the following properties.
The root of $\mathfrak T$ is a simplex with the door $\mathcal C$.
If a curve $\phi\subset\overline{P}$ exits a simplex
$S_0\in\mathfrak S$, it is either through the door
of $S_0$ or through an arc which is the door of a child of $S_0$
in $\mathfrak T$, and in the latter case, $\phi$ enters the child.
If $S_0$ has a parent in $\mathfrak T$
and $\phi$ exits $S_0$
through the door of $S_0$, then $\phi$ enters the parent.
\end{lemma}

\begin{proof
We first see that $\mathcal V\subseteq \mathcal S$.
Let a point $p\in \mathcal V$ be given.
There exists a curve $\phi\subset P$ from $p$ to a point
$q$ on $\partial P[s_\mathcal C,t_\mathcal C]$ which does not cross $\mathcal C$.
By Observation \ref{simplicesObservation}, $q$ is contained in a simplex of
$\mathfrak S$ and thus $q\in\mathcal S$. We
follow $\phi$ from $q$ to $p$. When $\phi$ exits a simplex,
it must enter another one by Observation \ref{simplicesObservation}
since $\phi$ does not cross
$\partialP[s(\mathcal C),t(\mathcal C)]$ or $\mathcal C$. Therefore,
$p\in \mathcal S$ as well.

It is straightforward to check that the constructed simplices
form a tree $\mathfrak T$ as described in the lemma.
\end{proof}

\begin{wrapfigure}[9]{r}{0.15\textwidth}
\vspace{-40pt}
\input{simplices.tex}
\caption{}
\label{simplicesFig}
\end{wrapfigure}

An example of the tree $\mathfrak T$ is given in Figure \ref{simplicesFig} for
case \cutDef c from Section \ref{cutDef}. The following lemma is the heart of our
proof of correctness. Recall that the curves in $\mathcal L^+$ are open,
oriented curves that turn to the left with curvature at most $1$.

\begin{lemma}\label{noLLinVV}
Let $\gamma$ be a curve in $\mathcal L^+$ contained in $\overline{P}$.
Let $\mathcal C$ be an arc specifying an area $\mathcal V$ to be removed from $P$ and
suppose that $\gamma$ starts at a point $a\in\mathcal C$.
If $\gamma$ leaves $\overline{\mathcal V}$ again, it
is through a point on $\mathcal C[s(\mathcal C),a]$.
\end{lemma}

\begin{proof}
Assume for contradiction that $\gamma$ leaves $\overline{\mathcal V}$ through a point not
as stated in the lemma.
Since the boundary of $\mathcal V$ is contained in $\partialP\cup\mathcal C$,
$\gamma$ leaves $\overline{\mathcal V}$ from a point on $\mathcal C(a,t(\mathcal C)]$.
Consider the tree
$\mathfrak T$ as described in Lemma \ref{simplexTree}.
Let $S$ be a simplex with maximum distance in $\mathfrak T$ to the root
such that $\gamma$ enters $S$.
Let $D$ be the door of $S$ and $s(D)$ and $t(D)$
be the beginning
and end of $D$ in counterclockwise order, respectively. Let $\mathcal D$
be the open disk such that $D$ is an arc on the circle $\partial\mathcal D$.
It follows from Lemma \ref{simplexTree} that the first time
$\gamma$ enters $S$, it is through a point on $D$.
Let $e\in D$ be the point closest to $s(D)$ such that $\gamma$ eventually
enters $S$ through $e$.
After $e$, $\gamma$ must leave $S$
through a point $f$ on $D(e,t(D)]$, since otherwise $\gamma$
enters the interior of the closed, simple curve defined by
$\gamma[a,e]$, $D[s(D),e]$, $\partialP[s(\mathcal C),s(D)]$,
and $\mathcal C[s(\mathcal C),a]$, which it cannot exit again by assumption.
Hence, Theorem \ref{mainThm} implies that the region bounded by
$\partial \mathcal D[f,e]$
and $\gamma[e,f]$ contain a unit disk different from
$\mathcal D$. That contradicts the simplex condition of $S$.
\end{proof}

By the following lemma, we conclude that when the algorithm terminates,
$\overline{P}$ is the maximum subset of $\overline{P_1}$ of bounded
conve curvature.
The lemma follows easily from Lemma
\ref{noLLinVV}.

\begin{lemma}\label{algOptimal}
For every $i=1,2,\ldots$, $\overline{P_i}$ contains
$Q$ for every set $Q\subset\overline{P_1}$ of bounded convex curvature.
\end{lemma}

\begin{proof
Let $Q\subset\overline{P_1}$ be a set of bounded convex curvature.
We prove the lemma by showing that each time we perform a cut by removing
some set $\mathcal V$ from $P$, $\mathcal V$ is disjoint from $Q$.

Consider for contradiction the first iteration in which
$Q$ is not disjoint from $\mathcal V$.
If $Q\subseteq\mathcal V$, then, by Corollary \ref{UCinL}, $Q$ contains an open
unit-disk $D$. From the simplex condition, we know that no simplex in
$\mathfrak S$ contains $D$. Therefore, we may consider the simplex $S$
with maximum distance to the root that contains a part of $\partial D$ and proceed
as in the proof of Lemma \ref{noLLinVV} to get a contradiction.

If not $Q\subseteq\mathcal V$, consider the first point $a\in\mathcal C$
where $\partialQ$ enters $\overline{\mathcal V}$ when following $\mathcal C$ from $s(\mathcal C)$. $\partialQ$ must exit $\overline{\mathcal V}$ through a point on
$\mathcal C(a,t(\mathcal C)]$, which contradicts Lemma \ref{noLLinVV}.
\end{proof}

\subsection{Proof of Lemma \ref{sepCrit}}\label{sepCritProof}

The following lemma is necessary to prove Lemma \ref{sepCrit}.

\begin{lemma}\label{arcsMostPi}
The arc $\mathcal C$ specifying a cut spans an angle of at most $\pi$.
Therefore, the same holds for every cut arc of $\partialP$.
\end{lemma}

\begin{proof}
Assume that $\mathcal C$ spans an angle of more than $\pi$.
Consider the curve $\xi=\xi(A_0,A_1,x_0)$
and the associated clearance circles $C_x$ and projections
$\Pi_0$ and $\Pi_1$ used to define $\mathcal C$.
Let $x_3$ be the center of $\mathcal C$. Then
$\mathcal C=C_{x_3}[\Pi_0(x_3),\Pi_1(x_3)]$. Let $x_1$ be the first point
in the first interval of $\xi$ that contains $x_3$ (since the intervals overlap at the
endpoints, there might be more intervals containing $x_3$).
Note that $C_{x_1}$ has radius less than $1$ since otherwise,
we would have chosen $x_3=x_1$.
Let $S$ be the simplex associated to the pair $(x_1,x_3)$ (using Lemma
\ref{simplexLemma})
and let
$U$ be the open unit-disk bounded by $C_{x_3}$.
Since $\mathcal C$ spans an angle of more than $\pi$, there exists unit-disks
in $S\cup U$ different than $U$, contradicting the simplex condition.
\end{proof}

\begin{proof}[Proof of Lemma \ref{sepCrit}]
Consider the smallest $i$ for which an arc $A$ of $\partialP_1$ exists such that
subsets of $A$ appear as arcs on the boundary of
more than one connected component of $P_{i+1}$.
Let $\mathcal C$ be the arc specifying the
set $\mathcal V$ such that $P_{i+1}=P_i\setminus\mathcal V$.
Since subsets of $A$ appear on more than one component of $P_{i+1}$,
a part of $A$ is removed from the boundary of $P_i$ by the cut.
This means that $\mathcal C$ intersects $A$ in points $a$ and $b$ when
following $\mathcal C$ in counterclockwise order, and the part
$A(a,b)$ is not on $\partialP_{i+1}$.
$A$ appears on the boundary of three
regions $R_1,R_2,R_3$ of $P_i\setminus\mathcal C$, where
$A[a,b]$ is an arc on $\partial R_2$, $\partial R_1$ contains $s(A)$,
and $\partial R_3$ contains $t(A)$. It could be possible that $R_1=R_3$,
but it does not make a difference for this proof.

Let $C$ be the circle on which $\mathcal C$ is an arc. The arc
$A(a,b)$ is either in the interior
or the exterior of $C$. Assume first that $A(a,b)$ is in the interior.
Note that parts of $\mathcal C$ are concave arcs on the boundary of $R_1$ and $R_3$.
Therefore, if $R_2$ is the only region among $R_1,R_2,R_3$
which is removed from $P_i$, there would be concave
cut arcs on $\partialP_{i+1}$,
contradicting Lemma \ref{cutArcCCW}.

Consider now the case where $A(a,b)$ is in the exterior of $C$.
We may assume that all arcs of $\partialP_1$ span an angle of at most $\pi$.
If an arc spans a larger angle, we can divide it into two arcs each spanning at most
$\pi$ by adding a vertex in the middle of the arc and thus at most doubling the
size of the input.
Since $\mathcal C$ spans an angle of at most $\pi$ by Lemma \ref{arcsMostPi}
and the same holds for $A$, the radius of $A$ must be less than $1$.
Assume for contradiction that $A$ is convex.
Since $R_2$ is removed from
$P_i$, a part of $P_i(s(\mathcal C),t(\mathcal C))$ appear on
$\partial R_2$.
$\mathcal C[a,b]$ and $A[a,b]$ form a closed, simple curve $J$.
If $\partialP_i(s(\mathcal C),t(\mathcal C))$
did not cross $\mathcal C[a,b]$, $R_2$ would be the interior of $J$ and $R_2$ would not
be removed from $P_1$. We can therefore consider the point
$x$ where $\partialP_i(s(\mathcal C),t(\mathcal C))$
enters $J$ for the first time
and the point $y$ where it leaves $J$ for the last time. $y$ must be on
$A(a,x)$, since $P_i$ is to the left of $\partialP_i$. If
$\partialP_i(s(\mathcal C),x)$ is disjoint from $\mathcal C$,
the curves $\partialP_i[s(\mathcal C),x]$ and $\mathcal C[s(\mathcal C),x]$ form a simple, closed
curve that separates $t(\mathcal C)$ from the points
on $\partialP_i[s(\mathcal C),x]$ in a neighborhood after $y$.
Therefore, $\partialP_i(y,t(\mathcal C))$
must cross $\mathcal C(s(\mathcal C),a)$ in order to get to $t(\mathcal C)$. Hence,
there are at least five points in
$\partialP_1[s(\mathcal C),t(\mathcal C)]\cap \mathcal C$. If
$\partialP_1(s(\mathcal C),x)$ crosses $\mathcal C$ somewhere, there are also at least
five intersection points.
Therefore, $\partialP_1[s(\mathcal C),t(\mathcal C)]$ must consist of at least
three arcs, since there are at most two intersection points between two arcs which are
not one the same circle.
On the other hand, we know from the definition of $\mathcal C$ that
there can be at most three such arcs.
Denote the arcs $B_0,B_1,B_2$ in the order in which they appear
on $\partialP_1[s(\mathcal C),t(\mathcal C)]$,
where $B_1=\sigma$ is the cut arc that was picked from $\Sigma$.
Assume first that $x\in B_0$. Since either $B_0$ and $B_1$ are tangential, or
$s(B_1)$ is a convex vertex, it is clear that $y$ has to be on $\mathcal C(x,b)$, which is a contradiction.
It is also impossible that $x\in B_2$, since in that case, $B_2$ should have
four intersection points with $\mathcal C$.

Assume then that $x\in B_1$. Since $B_1$ and $\mathcal C$ both have radius $1$,
the angle of the arc on $B_1$ from a point where it exits $C$
to the point where it enters $C$ would be more than $\pi$. Hence,
$B_1$ does not leave the interior of $J$ again. Then $B_2$ must have
three intersection points with $\mathcal C$, which is a contradiction.

Hence, if parts of $A$ appear on the boundary of more than one component
of $P$, $A$ must be a concave arc with radius lass than $1$.
\end{proof}

\subsection{Proof that Algorithm \ref{roundAlg} performs a linear
number of iterations}

Since the set $\mathcal V$ that we remove from $P$ is contained in one
connected component of $P$, the algorithm
only makes changes to one connected component of $P$ at a time.
A vertex $v$ of $\partial P$ is \emph{improper} if $v$ is a convex vertex
and $v$ is not a vertex of $\partialP_1$.
An improper vertex can be introduced
in two different ways:
1) If the arc $\mathcal C$ specifying a cut intersects a cut arc and the intersection point $v$ is on
$\partial\mathcal V$, then $v$ becomes a convex and hence improper vertex.
2) If the arc $\mathcal C$ begins or ends at the endpoint $v\notin\partialP_1$
of a cut arc which is not a convex vertex, $v$ might be a convex and hence improper vertex after the cut has been performed.

Consider the first time an improper vertex appears. Let $v$ be the vertex
and let $K$ be the connected component such that $v\in\partialK$.
Then $v$ will be removed by the subsequent cut performed in $K$ since
a cut arc with an endpoint at $v$ is closest to the top of $\Sigma$ among all objects
in $\Sigma\cap \partial K$.
It follows inductively that
there can be one or two improper vertices in each component, and
after the next iteration performed in the component, none of them
will be left.

A vertex $v$ of $\partialP$ which is not a point on $\partialP_1$
(note the difference between being a \emph{vertex} of $\partialP_1$ and being
a \emph{point} on $\partialP_1$)
can only be created if the arc $\mathcal C$
specifying a cut to be performed in $P$
intersects a cut arc at $v$.
It follows that $v$ is a convex and hence improper vertex.
Equivalently, every proper vertex is on $\partialP_1$.

Consider an endpoint $c$ of the arc $\mathcal C$ specifying a cut to be performed
in $P_i$, where $P_{i+1}=P_i\setminus\mathcal V$.
If $c$ is an inner point of an arc $A$ of $\partialP_i$,
Lemma \ref{cutArcCCW} together with
Observation \ref{oscSmallRadius} gives that $A$ is not a cut arc
since the circle containing $\mathcal C$ osculates $A$ at $c$.
Hence, $A$ is (a subset of) an arc of $\partialP_1$ and
$c\in\partialP_1$.
Furthermore, due to the way $\mathcal C$ is defined, an improper vertex of $\partialP_i$
will never be chosen as $c$.
Also in this case, we get that $c$ is on $\partialP_1$.
We summerize these observations in the following lemma.

\begin{lemma}\label{properness}
\begin{enumerate}[noitemsep,nolistsep]
\item
There are at most two improper vertices of $\partialK$ for
each connected component $K$ of $P$.
If there are two, they are endpoints of the same cut arc.

\item
All improper vertices of $\partialK$, where
$K$ is a connected component of $P$, are removed by the following cut performed
in $K$.

\item
The endpoints $s(\mathcal C)$ and $t(\mathcal C)$ of an arc $\mathcal C$ specifying
a cut are both points on $\partial P_1$.
\end{enumerate}
\end{lemma}

\begin{lemma}\label{linearIts}
The algorithm performs $O(n)$ iterations.
\end{lemma}

\begin{proof
We divide the iterations into the types \ref{t1}--\ref{t5} defined below
and prove that there is a linear number of each type.
We bound the iterations of type \ref{t1} by observing that each
such iteration corresponds to introducing an
edge in a planar multigraph with $2n$ vertices, where
each pair of vertices can be connected by at most $O(1)$ edges.
Hence, Euler's formula implies that $O(n)$ edges are created in total.
The iterations of types \ref{t2}--\ref{t5} can be bounded by the number of
iterations of type \ref{t1} or by observing that each iteration completely removes
one of the objects of $\partialP_1$ from $\partialP$. Hence there are $O(n)$ of each type.

Consider what happens during iterations $i$ when the algorithm picks an object
$\sigma$ from $\Sigma$.
Let $\mathcal V$ be the set removed from $P_i$ during the iteration,
i.e., $P_{i+1}=P_i\setminus\mathcal V$,
where possibly $\mathcal V=\emptyset$.
Lemma \ref{properness} implies that
the iteration is of one of the following types.
\begin{enumerate}[noitemsep,nolistsep]
\item\label{t1}
$\mathcal V$ is specified by an arc $\mathcal C$ and each endpoint of $\mathcal C$ is
either a vertex of $\partialP_1$ or an inner point of an arc of
$\partialP_1$ which is not a vertex of $\partialP_i$.

\item\label{t2}
$\mathcal V$ is specified by an arc $\mathcal C$ and one or both
endpoints of $\mathcal C$ is a vertex $v$ of $\partialP_i$ which is not a vertex
of $\partialP_1$. Hence, such a vertex $v$ is the endpoint of a cut arc
of $\partialP_i$.

\item\label{t3}
A complete connected component $K$ is removed from $P$, i.e., $\mathcal V=K$.

\item\label{t4}
$\mathcal V=\emptyset$ and nothing happens since $\sigma$ is not anymore on $\partialP$.

\item\label{t5}
$\mathcal V=\emptyset$ and nothing happens since $\sigma$ is a perfect cut arc.
\end{enumerate}

Consider cuts of type \ref{t1}. We see that each such cut corresponds to
adding an edge to a planar graph $G$ with $2n$ nodes.
There is one node in $G$ for each arc and vertex of $\partial P_1$.
We choose a curve $\phi$
from $s(\mathcal C)$ to $t(\mathcal C)$ contained in $\mathcal V$ as the edge corresponding to the cut.
This is possible since $\mathcal V$ is connected by Lemma
\ref{VVConnected}.
A vertex $v$ of $\partialP_1$ is incident to $\phi$ if
$v$ is an endpoint of $\phi$.
An arc $A$ of $\partialP_1$ is incident to $\phi$ if an endpoint of $\phi$ is an inner
point of $A$.
Let $A_0$ and $A_1$ be the objects of $\partialP_1$ incident to $\phi$
such that $s(\mathcal C)\in A_0$ and
$t(\mathcal C)\in A_1$. Let $C$ be the circle containing $\mathcal C$.
Observe that if $A_0$ (resp.~$A_1$) is an arc, then
$C$ osculates $A_0$ at $s(\mathcal C)$ (resp.~$A_1$ at $t(\mathcal C)$).

We say that $A_0$ and $A_1$ are \emph{parallel} if:
\begin{itemize}[noitemsep,nolistsep]
\item
$A_0$ and $A_1$ are concentric arcs, one is concave,
the other is convex, and the radius of
the convex is $2$ larger than the radius of the concave.

\item
$A_0$ and $A_1$ are
two parallel line segments (in the ordinary sense) with opposite directions and
distance $2$.

\item
$A_1$ (resp.~$A_0$) is a vertex while
$A_0$ (resp.~$A_1$) is convex arc with radius $2$
and center $A_1$ (resp.~$A_0$).
\end{itemize}

If $A_0$ and $A_1$ are parallel, there are infinitely many unit-circles
that osculates $A_0$ or $A_1$ like $C$ does.
Otherwise,
there are only $O(1)$. Hence, by Euler's formula,
we are adding $O(n)$ edges to $G$ that connect
non-parallel objects.

We now verify that even if $A_0$ and $A_1$ are parallel, we make
$O(1)$ edges between them in $G$.
Consider the first case where $A_0$ and $A_1$ are concentric,
$A_0$ is convex, $A_1$ is concave, and the radius of $A_0$ is $2$ larger
than the radius of $A_1$.
The other types of parallel arcs are handled in a similar way.
We consider the case where more than one cut arc is
made during the execution of the algorithm
which starts on $A_0$, ends on $A_1$, and is tangential to both arcs.
Assume that the first such arc is $\mathcal C_1$ from
$s(\mathcal C_1)\in A_0$ to $t(\mathcal C_1)\in A_1$ created during iteration $i$.
Consider the next time where such a cut arc $\mathcal C_2$ is made from
$s(\mathcal C_2)\in A_0$ to $t(\mathcal C_2)\in A_1$ during iteration $k$, $k>i$.
The boundary interval $\partialP_{i+1}[s(\mathcal C_2),t(\mathcal C_2)]$ contains
no convex vertices or convex arcs of radius less than $1$. Therefore,
some cut arc must have introduced a convex vertex on
$\partialP(s(\mathcal C_2),t(\mathcal C_2))$.
Hence, during some iteration $l$, where $i<l<k$,
a cut arc $B$ is introduced from
$x\in\partialP_{i+1}(s(\mathcal C_2),t(\mathcal C_2))$ to
$y\in\partialP_{i+1}(x,t(\mathcal C_2))$, where
$\mathcal B(x,y)\subsetP_{i+1}$.
From Lemma \ref{cutArcCCW} we know that $B$ is convex
when traversed from $x$ to $y$. But such an arc $B$ does not exists
for any $x\inP_{i+1}(s(\mathcal C_2),t(\mathcal C_2))$ due to the assumptions
on $A_0$ and $A_1$.
Therefore, neither $B$ nor $\mathcal C_2$ can appear as cut arcs and the number
of edges between $A_0$ and $A_1$ in $G$ is $O(1)$.

In a similar way, we see that the total number of perfect cut arcs created
while executing the algorithm is $O(n)$ by describing a planar graph $H$.
The vertex set of $H$ is also the vertices and arcs of $\partialP_1$.
If a cut creates a new cut arc $\mathcal C'\subseteq\mathcal C$
of $\partialP_{i+1}$ which is perfect, we add the edge $\mathcal C'$ to $H$.
An endpoint of $\mathcal C'$
cannot be an interior point of a cut arc since $\mathcal C'$ is perfect.
Therefore, $s(\mathcal C'),t(\mathcal C')\in P_1$.
Hence, we can bound the number of edges in $H$ in a similar way
as the number of edges in $G$.

We say that a cut arc is \emph{active} if it is in $\Sigma$.
We see inductively that there can be at most one active cut arc in each connected
component of $P$. Namely, assume that there is one active
cut arc $\mathcal C$ in the component $K$ of $P$.
Assume that iteration $i$ is the following iteration performed in $K$.
We must have $\sigma=\mathcal C$, since $\mathcal C$ was added to the top of
$\Sigma$ when it was created.
During the iteration, $\mathcal C$ either disappears from $\partialP$
when removing $\mathcal V$
or no change to $P$ is made since
$\mathcal C$ is perfect. This means that all inactive cut arcs are perfect.

Consider now a cut of type \ref{t2}. Assume that an endpoint of $\mathcal C$ is
an endpoint of a cut arc $A$ of $\partialP_i$.
The cut arc $A$ is inactive and hence
perfect. After the cut, $v$ is a convex vertex. After one more iteration in the component
containing $A$, $A$ will not anymore be an arc of
$\partialP$. Hence, there are at most $2$ iterations of type \ref{t2} for any perfect
arc, so there are $O(n)$ iterations of type \ref{t2}.

Consider a cut of type \ref{t3}. Let $K$ be the component removed by the
cut. Note that there are at most three arcs on $\partialK$.
Assume first that there are at least two cut arcs on $\partialK$.
One of them is not active and is hence perfect. Therefore, there can be removed
at most $O(n)$ such components $K$.
Assume now that there is at most one cut arc on $\partialK$. If there
are three arcs on $\partialK$, there is also a vertex of $\partialP_1$.
It can happen at most $n$ times that such a component is removed.
The only remaining case is that $\partialK$ consists of one cut arc $\mathcal C$ and
an arc $A'$ which is a subset of an arc $A$ of $\partialP_1$.
$A'$ must be a convex arc,
a line segment, or a concave arc with radius more than $1$.
Therefore, by Lemma \ref{sepCrit}, there is no other connected component of $P$ where
another subset of $A$ is an arc. Hence, there can be removed at most $n$ such
components $K$.

Consider an iteration of type \ref{t4}. If $\sigma$ is not anymore on
$\partialP$, $\sigma$ must be an object of $\partialP_1$, since
every active cut arc is the uppermost object in $\Sigma$ among all objects
of the same connected component of $P$ as $\sigma$. Therefore, there are
at most $2n$ iterations of this type.

Consider the iterations of type \ref{t5}. As we saw before, there
are made $O(n)$ perfect cut arcs during the execution of the algorithm,
which bounds the number of this type.
\end{proof}

Since every cut arc is eventually picked from $\Sigma$ by Algorithm
\ref{roundAlg}, the linear bound on the number of iterations leads to the following
lemma.

\begin{lemma}\label{linearCutArcs}
The total number of cut arcs created while running Algorithm \ref{roundAlg}
is $O(n)$. Likewise, the total number of different vertices appearing on $\partialP$
while running Algorithm \ref{roundAlg} is $O(n)$.
\end{lemma}

We have now proved the following theorem.

\begin{theorem}\label{LTThm}
Given a simply-connected open region $P_1$ bounded by a curvilinear polygon
consisting of $n$ line segments and circular arcs,
there is a unique maximum set $Q\subseteq\overline{P_1}$
of bounded convex curvature
which contains every set $Q'\subseteq\overline{P_1}$
of bounded convex curvature.
$\partialQ$ consists of $O(n)$ line segments and circular arcs, and
Algorithm \ref{roundAlg} computes $Q$ in $O(n)$ iterations.
\end{theorem}

\section{Implementation}\label{anImplementation}

In this section, we show how the algorithm can be implemented so
that it uses $O(n\log n)$
time in total and $O(n)$ space.

Let $\mathcal C$ be the arc specifying a cut to be performed in $P$.
Let $R_1,\ldots,R_r$ be the connected components of
$P\setminus\mathcal C$, and assume without loss of generality that
the sets $R_1,\ldots,R_s$, $s\leq r$, have to be removed since their boundaries
contain a part of $\partialP(s(\mathcal C),t(\mathcal C))$.
For ease of presentation we assume that $\mathcal C$ contains no vertices of
$\partialP$ except for possibly the endpoints $s(\mathcal C)$ and $t(\mathcal C)$.
Algorithm \ref{performCut} traverses the boundary of each of the regions
$R_1,\ldots,R_s$ and introduces the new cut arcs in order to remove
the regions from $P$.

\begin{algorithm}[h]
\LinesNumbered
\DontPrintSemicolon
\SetArgSty{}
\SetKwInput{Input}{Input}
\SetKwInput{Output}{Output}
\SetKw{Report}{report}
\SetKwIF{If}{ElseIf}{Else}{if}{}{else if}{else}{end if}
\SetKwFor{Foreach}{for each}{}{end for}
\SetKwFor{While}{while}{}{end while}
$U\gets\{s(\mathcal C)\}$.\;
\While {$U\neq\emptyset$} {
    Remove a point $e$ from $U$. If $e$ is not a vertex of $\partialP$, create a vertex at $e$.\;\label{picke}
    $a\gets e$.\;
    \Repeat{$a=e$}{\label{removeRegion}
        Let $b\gets \ttt{TraverseP}(\mathcal C,a,e)$. If $b$ is not a vertex of $\partialP$, create a vertex at $b$.\;
        Mark all objects on $\partialP[a,b]$ as removed, except for vertices $a$ and $b$.\;
        If $b\in\partialP(s(\mathcal C),t(\mathcal C))$, add $b$ to $U$.\;
        \uIf {$\mathcal C$ enters or leaves $P$ at $b$} {
            $a\gets\ttt{TraverseC}(\mathcal C,b)$. If $a$ is not a vertex of $\partialP$, create a vertex at $a$.\;
            Change $\partialP$ by setting the arc succeeding $a$ and preceding $b$
            to $\mathcal C[a,b]$.\;
        } \Else {
            $a\gets e$.\;
        }
    }
}
\caption{$\ttt{PerformCut}(\mathcal C)$}
\label{performCut}
\end{algorithm}

The algorithm traverses $\partialP(s(\mathcal C),t(\mathcal C))$ from $s(\mathcal C)$
and removes the regions $R_1,\ldots,R_s$ one by one.
Each point in the set $U$ is on the boundary of one of the regions
$R_1,\ldots,R_s$ which has not
so far been removed. The loop at line \ref{removeRegion} traverses one such region.

The subroutine $\ttt{TraverseP}(\mathcal C,a,e)$ traverses $\partialP$ from $a$ until we
meet $e$ or a point where $\mathcal C$ enters or exits $P$.
The point $b$ where we stop traversing is returned.

The subroutine $\ttt{TraverseC}(\mathcal C,b)$ follows $\mathcal C$ from $b$ through $P$ until
it exits $P$ at some point $a$, which is returned.
Since we assumed that no vertex of $\partialP$ is an inner point of $\mathcal C$,
it is uniquely defined which direction of $\mathcal C$ to follow.

Since $P$ is simply-connected, the regions
$R_1,\ldots,R_r$ induce a tree $T$ such that there is an edge in $T$ between
two regions $R_j$ and $R_k$
if there is an arc $\mathcal C(x,y)\subset\partial R_j\cap\partial R_k$ for $x\neq y$.
By Lemma \ref{VVConnected},
$\mathcal V$ is connected, so the regions $R_1,\ldots,R_s$
induce a subtree in $T$. Therefore, each of the regions in $T$
is traversed at least once by
Algorithm \ref{performCut}. On the other hand, a region is removed
from $P$ while its boundary is traversed, so each region is traversed
at most once. Hence, we have the following lemma.

\begin{lemma}
Algorithm \ref{performCut} traverses the boundary of each region $R_1,\ldots,R_s$
exactly once and thus correctly computes $P\getsP\setminus\mathcal V$ as
specified by the arc $\mathcal C$.
\end{lemma}

The point $\ttt{TraverseC}(\mathcal C,b)$ is the first intersection point
between $\mathcal C$ and $\partialP$ when following $\mathcal C$ from
$b$ in the relevant direction.
Cheng et al.~\cite{Cheng04} describes an efficient solution to the following
problem.
For a simple polygon $V$, preprocess $V$ such that queries of the following
kind can be answered efficiently: Given a circular unit-radius arc beginning
at some point in the interior of $V$, find the first intersection point between the arc and
$V$ if it exists. The algorithm requires $O(n)$ space,
uses $O(n\log n)$ time on preprocessing, and
answers queries in $O(\log n)$ time, where $n$ is the number of vertices
of $V$.

It is straightforward to generalize the method of Cheng et al.~to
curvilinear polygons.
We apply the preprocessing to the original input $\partialP_1$.
Thus, by querying an arc following $\mathcal C$ from $b$ in the direction through $P$, we
know the point where $\mathcal C$ exits $P_1$.
However, the arc
$\mathcal C$ can exit $P$ before it exits $P_1$, namely
if and only if it crosses a cut arc of $\partialP$.
In the following, we show how to detect if that is the case or not.

Since $\mathcal C$ enters or exits $P$ at $b$, there exists a point $d\in\mathcal C\capP$
such that $\mathcal C(d,b)\subsetP$. In the following, $d$ denotes such a point.
It is not necessary to compute $d$, it is merely a tool in our analysis.
We know from Lemma \ref{properness} that
$s(\mathcal C),t(\mathcal C)\in\partialP_1$.
Using the circular ray shooting data structure, we can find a closed subset
$\mathcal C'\subseteq\mathcal C$ such that
$s(\mathcal C'),t(\mathcal C')\in\partialP_1$,
$\mathcal C'(s(\mathcal C'),t(\mathcal C'))\subsetP_1$,
and $b\in\mathcal C'$. Hence also $d\in\mathcal C'$. The following lemma says that
if the arc $\mathcal C'$, when traversed in any direction from $d$,
enters a removed area, i.e., a connected component of $P_1\setminusP$,
then it stays in that removed area.

\begin{lemma}\label{charArcB}
Let $x$ be one of the endpoints of $\mathcal C'$.
There is at most one cut arc $A$ of $\partialP$ which intersects $\mathcal C'(d,x)$.
There is such an arc
$A$ if and only if $x\notin\partialP$.
If $A$ exists, $\mathcal C'(d,x)$ and
$A$ intersect at a unique point $y$, and
$\mathcal C'[y,x)\subsetP_1\setminusP$.
\end{lemma}

\begin{proof
Assume first that there is a cut arc $A$ of $\partialP$ intersecting $\mathcal C'(d,x)$
at a point $y$. Assume for contradiction that $\mathcal C'(y,x)$ intersects
a cut arc of $\partialP$ at a point $z$. $\mathcal C'$ exits $P$ at $y$ and enters $P$ at
$z$. We may consider the smallest $i$ such that $\mathcal C'(d,x)$ contains an interval
$\mathcal C'[y,z]$ which is outside $P_{i+1}$. Thus, $\mathcal C'[y,z]\subset\mathcal V$, where
$P_{i+1}=P_i\setminus\mathcal V$.
Let $B$ be the arc that specifies the set $\mathcal V$.
Consider the intersection point $w\inB\cap\mathcal C'(d,x)$ where
$\mathcal C'(d,x)$ enters or leaves $\mathcal V$ which is closest to $s(B)$.
Note that $\mathcal C'$ is a curve in $\mathcal L^+$
independently of the direction in which we traverse $\mathcal C'$.
Therefore, Lemma \ref{noLLinVV} gives that when following $\mathcal C'$ into $\mathcal V$ from
$w$, the point where it exits $\mathcal V$ is on $B[s(B),w)$.
That is a contradiction since $w$ was as close to $s(B)$ as possible.
Hence, from $y$ an on, $\mathcal C'$ is contained in $P_1\setminusP$ and
$x\notin\partialP$.

On the other hand, if $\mathcal C'(d,x)$ does not intersect any cut arc of $\partialP$, then
$\mathcal C(d,x)$ is contained in $P$ and therefore $x\in\partialP$.
\end{proof}

It is possible that $\mathcal C'(s(\mathcal C'),d)$ and $\mathcal C'(d,t(\mathcal C'))$ intersect the same
cut arc $B$. That is easy to detect since we are given a point
$b\in\partialP\cap\mathcal C'$
where $\mathcal C'$ enters of leaves $P$. Thus, we check if $b$ is on a cut arc
$B$ and if $\mathcal C(b,x)$ intersects the same arc. Otherwise, every cut
arc $A$ satisfies that
$A\cap \mathcal C'(s(\mathcal C),d)=\emptyset$ or
$A\cap \mathcal C'(d,t(\mathcal C))=\emptyset$,
and we have the following lemma.

\begin{lemma}\label{charArcB2}
Let $A$ be a cut arc of $\partialP$ such that
$s(A),t(A)\in\partialP_1$. Assume that
$A\cap \mathcal C'(s(\mathcal C'),d)=\emptyset$ or
$A\cap \mathcal C'(d,t(\mathcal C'))=\emptyset$.
Then, the following two statements hold:
\begin{itemize}[noitemsep,nolistsep]
\item
$A$ and $\mathcal C'(s(\mathcal C'),d)$ intersect
if and only if
the endpoints of $\mathcal C'$ and $A$ appear in the order
$s(\mathcal C'),t(A),t(\mathcal C'),s(A)$
on $\partialP_1$.

\item
$A$ and $\mathcal C'(d,t(\mathcal C'))$ intersect
if and only if
the endpoints of $\mathcal C'$ and $A$ appear in the order
$s(\mathcal C'),s(A),t(\mathcal C'),t(A)$
on $\partialP_1$.
\end{itemize}
\end{lemma}

\begin{proof
We prove the first statement. The second follows from similar arguments.
Assume that $A$ and $\mathcal C'(s(\mathcal C'),d)$ intersect at a point $a$.
By Lemma \ref{charArcB}, we know that $\mathcal C'(s(\mathcal C'),a)$
does not intersect $A$.
Since $\mathcal C'(b,t(\mathcal C'))$ does not intersect $A$ by assumption,
the endpoints of $\mathcal C'$ are on different sides of $A$ in $P_1$.
$A$ divides $P_1$ into two regions, one with a boundary
including $\partialP_1(s(A),t(A))$
and the other with a boundary including
$\partialP_1(t(A),s(A))$.
The portion $\mathcal C'(s(\mathcal C'),a]$ is outside $P$. Hence $\mathcal C'$ enters $P$
at $a$, so Lemma \ref{cutArcCCW} gives that
$s(\mathcal C')\in\partialP_1(s(A),t(A))$ and
$t(\mathcal C')\in\partialP_1(t(A),s(A))$,
or, equivalently, that the order of the points are as stated in the lemma.

If the order of the endpoints is as stated,
the endpoints of $\mathcal C'$ are on different sides of $A$, and hence
$\mathcal C'$ and $A$ intersect at some point $a$. Lemma \ref{charArcB}
gives that $\mathcal C'(s(\mathcal C'),a]\subsetP_1\setminusP$. Hence,
$a\in\mathcal C'(s(\mathcal C'),d)$.
\end{proof}

\begin{wrapfigure}[6]{r}{0.15\textwidth}
\vspace{-30pt}
\centering
\input{cutArcIntersect.tex}
\caption{}
\label{cutArcIntersectFig}
\end{wrapfigure}

See Figure \ref{cutArcIntersectFig}, which illustrates Lemma
\ref{charArcB2}.
The black arc $A$ is the only cut arc of $\partialP$.
The thick part of the grey arc $\mathcal C$ is $\mathcal C'$.

Lemma \ref{charArcB2} leads to our method for finding cut arcs intersecting
an arc $\mathcal C'$ by searching after arcs with endpoints on specific portions of
$\partialP_1$.
We associate to each point $p$ on $\partialP_1$ a unique number
$\varphi(p)\in[0,n)$. Let the vertices of $\partialP_1$ be
$v_0,v_1,\ldots,v_{n-1},v_n$, where $v_0=v_n$. We set
$\varphi(v_i)=i$ for $i<n$.
For the points $p$ on the arc between two vertices $v_i$ and
$v_{i+1}$, we interpolate between $i$ and $i+1$ to uniquely define $\varphi(p)$.
For an arc $A$ with $s(A),t(A)\in\partialP_1$,
we define an associated point $\theta(A)\in[0,n)\times(0,2n)$
in the following way:
$$
\theta(A)=
\begin{cases}
(\varphi(s(A)),\varphi(t(A))) & \textrm{if }\varphi(s(A))<\varphi(t(A)) \\
(\varphi(s(A)),\varphi(t(A))+n) & \textrm{otherwise}.
\end{cases}
$$

Lemma \ref{charArcB2} then leads to the following.

\begin{lemma}\label{charArcB3}
Let $A$ be a cut arc of $\partialP$ such that
$s(A),t(A)\in\partialP_1$.
Assume that
$A\cap \mathcal C'(s(\mathcal C'),d)=\emptyset$ or
$A\cap \mathcal C'(d,t(\mathcal C'))=\emptyset$.
Let $\theta(\mathcal C')=(x,y)$.

\begin{itemize}[noitemsep,nolistsep]
\item
$A$ and $\mathcal C'(s(\mathcal C'),d)$ intersect
if and only if
\begin{itemize}[noitemsep,nolistsep]
\item
$y<n$ and $\theta(A)$ is in $[0,x)\times (x,y)$ or $(y,n)\times (x+n,y+n)$, or

\item
$y\geq n$ and $\theta(A)$ is in $(y-n,x)\times (x,y)$.
\end{itemize}

\item
$A$ and $\mathcal C'(d,t(\mathcal C'))$ intersect
if and only if
\begin{itemize}[noitemsep,nolistsep]
\item
$y<n$ and $\theta(A)$ is in $(x,y)\times (y,x+n)$, or

\item
$y\geq n$ and $\theta(A)$ is in $[0,y-n)\times (y-n,x)$ or $(x,n)\times (y,x+n)$.
\end{itemize}
\end{itemize}
\end{lemma}

\begin{proof
Lemma \ref{charArcB2} says that $A$ and $\mathcal C'(s(\mathcal C'),d)$
intersect if and only if the endpoints of $\mathcal C'$ and $A$ appear in the order
$s(A),s(\mathcal C'),t(A),t(\mathcal C')$
on $\partialP_1$. If we assume that
$y<n$ and $\varphi(s(A))<\varphi(t(A))$,
this is equivalent to
$0\leq \varphi(s(A))<\varphi(s(\mathcal C'))<\varphi(t(A))
<\varphi(t(\mathcal C'))<n$, which means that
$\theta(A)\in [0,x)\times (x,y)$. The other cases follows in a similar way.
\end{proof}

For each cut arc $A$ of $\partialP$ where
$s(A),t(A)\in\partialP_1$, we store
the point $\theta(A)$ in a data structure $\Theta$.
It is necessary to add new points to and
delete points from $\Theta$ as the algorithm proceeds, since new
cut arcs are created and other no longer appear on $\partialP$.
We need to be able to find a point $\theta(A)$ in a rectangle
specified by $\mathcal C'$ as stated in Lemma \ref{charArcB3}.
Therefore, we implement $\Theta$ as a fully dynamic orthogonal
range searching structure as described by Blelloch \cite{blelloch2008space}.
Algorithm \ref{traverseC} sketches how to implement $\ttt{TraverseC}$.

\begin{algorithm}[h]
\LinesNumbered
\DontPrintSemicolon
\SetArgSty{}
\SetKwInput{Input}{Input}
\SetKwInput{Output}{Output}
\SetKw{Report}{report}
\SetKwIF{If}{ElseIf}{Else}{if}{}{else if}{else}{end if}
\SetKwFor{Foreach}{for each}{}{end for}
\SetKwFor{While}{while}{}{end while}
Use the circular ray shooting data structure to find the arc
$\mathcal C'\subseteq\mathcal C$ such that $\mathcal C'(s(\mathcal C'),t(\mathcal C'))\subsetP_1$,
$s(\mathcal C'),t(\mathcal C')\in\partialP_1$, and $b\in\mathcal C'$.\;
Let $z\in\{s(\mathcal C'),t(\mathcal C')\}$ be the endpoint of $\mathcal C'$
when following $\mathcal C'$ from
$b$ through $P$.\;
If $b$ is on a cut arc $B$ of $\partialP$ and $\mathcal C(b,z)$ intersects $B$
at a point $a$, return $a$.\;
Ask the data structure $\Theta$ if any point $\theta(A)$ is
in the rectangle(s) as specified by Lemma \ref{charArcB3}. If so,
return the intersection point between $A$ and $\mathcal C'(b,z)$.\;
Return $z$.\;
\caption{$\ttt{TraverseC}(\mathcal C,b)$}
\label{traverseC}
\end{algorithm}

It is now possible to bound
the running time and memory requirement
of Algorithm \ref{roundAlg} when using our suggested implementation.

\begin{theorem}\label{finalThm}
Algorithm \ref{roundAlg} can be implemented so that it runs in
time $O(n\log n)$ and uses $O(n)$ space.
\end{theorem}

\begin{proof
We first bound the space and time used on maintaining and querying the data structure
$\Theta$.
From Lemma \ref{linearCutArcs}, we know that there are $O(n)$ points in $\Theta$ at
any time. Blelloch \cite{blelloch2008space} describes how to implement
$\Theta$ using $O(n)$ space so that insertions and deletions are performed in
$O(\log n)$ amortized time and
orthogonal range reporting queries in
$O\left(\log n+k\frac{\log n}{\log \log n}\right)$
time, where $k$ is the number of reported points.
In our case, due to Lemma \ref{charArcB}, there is $0$ or $1$ point
to report in each query.
Therefore, we use $O(n\log n)$ time on $\Theta$ in total.

For each cut arc of $\partialP$, we perform $2$ circular ray shooting queries.
Thus, we use $O(n\log n)$ time on that in total.

The portion of $\partialP$ we traverse when calling
$\ttt{TraverseP}(\mathcal C,a,e)$ is removed from $P$ and hence never traversed again.
Therefore, the time used on $\ttt{TraverseP}$ is bounded by the number of
vertices occuring on $\partialP$ during the execution of the algorithm.
By Lemma \ref{linearCutArcs}, we use $O(n)$ time on $\ttt{TraverseP}$
in total.
\end{proof}

\section*{Acknowledgements}

We want to thank Jacob Holm, Ralph Howard, Mathias B\ae k Tejs Knudsen, and
Eva Rotenberg for useful suggestions and discussions

\bibliographystyle{plain}

redpajama_set_name: RedPajamaArXiv