}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S}(\pi)$.
Consequently, one of $I$ and $I^{\prime}$ has an angular coordinate in
$(0,\pi)$ and the other in $(\pi,2\pi)$. Thus, they are on opposite sides of
$\overleftrightarrow{OT}$.

It remains to show that $|\overline{PI}|$ and $|\overline{PI^{\prime}}|$
increase with $\hat{r}$. Consider two radii $r_{1},r_{2}$ with $r(T)\leq
r_{1}<r_{2}$. Let $I_{r_{1}}$ and $I_{r_{2}}$ denote the positions that the
intersection $I$ has at $\hat{r}=r_{1}$ and $\hat{r}=r_{2}$, respectively, and
let $I^{\prime}_{r_{1}}$ and $I^{\prime}_{r_{2}}$ be defined analogously.
Consider $\hat{r}=r_{1}$ first. By Lemma 4.4 the bisector $S\\!\perp\\!T$
intersects $\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$ at exactly the
points $I_{r_{1}}$ and $I^{\prime}_{r_{1}}$, meaning the line segment
$\overline{I_{r_{1}}I^{\prime}_{r_{1}}}$ lies in $\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$. Moreover, the
point $P$ lies in $\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$ and on
$S\\!\perp\\!T$, meaning $P\in\overline{I_{r_{1}}I^{\prime}_{r_{1}}}$ and thus
the line segments $\overline{PI_{r_{1}}}$ and $\overline{PI^{\prime}_{r_{1}}}$
are contained in $\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$. Now assume that
$\hat{r}$ increases to $\hat{r}=r_{2}$ but $|\overline{PI}|$ does not. (The
proof for $|\overline{PI^{\prime}}|$ is analogous.) Then
$I_{r_{2}}\in\overline{PI_{r_{1}}}$. However, since the beach ellipse
$\leavevmode\hbox to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$ at $\hat{r}=r_{1}$
is completely contained in $\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$ at $\hat{r}=r_{2}$
(Lemma 4.6), it follows that $I_{r_{2}}\in\overline{PI_{r_{1}}}$ is inside of
$\leavevmode\hbox to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$, contradicting the
fact that $I_{r_{2}}\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$.

Figure 7: Illustration of the proof of Lemma 4.10. The sites $S$ and
$S^{\prime}$ lie on the witness circle of $V$. The intersection
$I\in\leavevmode\hbox to5.04pt{\vbox
to6.31pt{\pgfpicture\makeatletter\hbox{\hskip 2.5198pt\lower-3.15587pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.31604pt}{2.95587pt}\pgfsys@curveto{0.43626pt}{3.34758pt}{-0.86613pt}{2.34174pt}{-1.59297pt}{0.70924pt}\pgfsys@curveto{-2.31981pt}{-0.92325pt}{-2.19582pt}{-2.56416pt}{-1.31604pt}{-2.95587pt}\pgfsys@curveto{-0.43626pt}{-3.34758pt}{0.86613pt}{-2.34174pt}{1.59297pt}{-0.70924pt}\pgfsys@curveto{2.31981pt}{0.92325pt}{2.19582pt}{2.56416pt}{1.31604pt}{2.95587pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.67812pt}{1.74374pt}\pgfsys@moveto{1.06561pt}{1.74374pt}\pgfsys@curveto{1.06561pt}{1.95775pt}{0.89212pt}{2.13124pt}{0.67812pt}{2.13124pt}\pgfsys@curveto{0.46411pt}{2.13124pt}{0.29062pt}{1.95775pt}{0.29062pt}{1.74374pt}\pgfsys@curveto{0.29062pt}{1.52974pt}{0.46411pt}{1.35625pt}{0.67812pt}{1.35625pt}\pgfsys@curveto{0.89212pt}{1.35625pt}{1.06561pt}{1.52974pt}{1.06561pt}{1.74374pt}\pgfsys@closepath\pgfsys@moveto{0.67812pt}{1.74374pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S\cap\leavevmode\hbox
to5.04pt{\vbox to6.31pt{\pgfpicture\makeatletter\hbox{\hskip
2.5198pt\lower-3.15587pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.31604pt}{2.95587pt}\pgfsys@curveto{0.43626pt}{3.34758pt}{-0.86613pt}{2.34174pt}{-1.59297pt}{0.70924pt}\pgfsys@curveto{-2.31981pt}{-0.92325pt}{-2.19582pt}{-2.56416pt}{-1.31604pt}{-2.95587pt}\pgfsys@curveto{-0.43626pt}{-3.34758pt}{0.86613pt}{-2.34174pt}{1.59297pt}{-0.70924pt}\pgfsys@curveto{2.31981pt}{0.92325pt}{2.19582pt}{2.56416pt}{1.31604pt}{2.95587pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.67812pt}{1.74374pt}\pgfsys@moveto{1.06561pt}{1.74374pt}\pgfsys@curveto{1.06561pt}{1.95775pt}{0.89212pt}{2.13124pt}{0.67812pt}{2.13124pt}\pgfsys@curveto{0.46411pt}{2.13124pt}{0.29062pt}{1.95775pt}{0.29062pt}{1.74374pt}\pgfsys@curveto{0.29062pt}{1.52974pt}{0.46411pt}{1.35625pt}{0.67812pt}{1.35625pt}\pgfsys@curveto{0.89212pt}{1.35625pt}{1.06561pt}{1.52974pt}{1.06561pt}{1.74374pt}\pgfsys@closepath\pgfsys@moveto{0.67812pt}{1.74374pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S^{\prime}$ that moves
towards $V$ lies on the angular bisector $\overrightarrow{V}$ (orange) of the
angle $\sphericalangle SVS^{\prime}$, since $\overrightarrow{V}$, $I,P$, and
$S$ are on the same side of $\overleftrightarrow{OV}$.

The above lemma has some interesting implications. Consider two sites $S,T$
that are incident to a Voronoi vertex $V$, meaning they lie on the arc of the
witness circle of $V$. Then, $V$ lies on the bisector $S\\!\perp\\!T$ and, in
particular, on one side of the point $P\in S\\!\perp\\!T$ defined in the
lemma. As the sweep circle expands, the intersections $I$ and $I^{\prime}$
move along the bisector and away from $P$, meaning exactly one of them reaches
$V$ eventually. More precisely, the following lemma captures from which
directions the intersections approach a Voronoi vertex. Recall that
$\sphericalangle ABC$ denotes the angle between $\overrightarrow{BA}$ and
$\overrightarrow{BC}$ in clockwise direction around $B$.

######  Lemma 4.10.

Let $V\in\mathcal{V}$ be a Voronoi vertex with far point $V^{\prime}$ and
incidence tuple $(S_{1},S_{2},S_{3})$. Further, let
$(S,S^{\prime})\in\\{(S_{1},S_{2}),(S_{2},S_{3}),(S_{1},S_{3})\\}$, let
$\overrightarrow{V}$ be the angular bisector of $\sphericalangle
SVS^{\prime}$, and let $I\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S^{\prime}$ be the
intersection with $I=V$ at $\hat{r}=r(V^{\prime})$. Then,
$I\in\overrightarrow{V}$ for $\hat{r}<r(V^{\prime})$.

######  Proof 4.11.

Note that $V$ divides $S\\!\perp\\!S^{\prime}$ into the two rays
$\overrightarrow{V}$ and $S\\!\perp\\!S^{\prime}\setminus\overrightarrow{V}$
and so does the line $\overleftrightarrow{OV}$. Thus, since $I\in
S\\!\perp\\!S^{\prime}$, it suffices to show that $I$ and $\overrightarrow{V}$
are on the same side of $\overleftrightarrow{OV}$. Without loss of generality,
assume $r(S)\geq r(S^{\prime})$. By Lemma 4.8 there is a point
$P=\overline{OS}\cap S\\!\perp\\!S^{\prime}$ such that
$I\in\overline{PV}\subset S\\!\perp\\!S^{\prime}$. Thus, $P$ and $I$ are on
the same side of $\overleftrightarrow{OV}$. Moreover, since
$P\in\overline{OS}$, we also know that $S$ and $I$ are on the same side of
$\overleftrightarrow{OV}$. Consequently, it suffices to show that
$\overrightarrow{V}$ is on the same side of $\overleftrightarrow{OV}$ as $S$,
as shown in Figure 7.

If $S^{\prime}$ is on the same side of $\overleftrightarrow{OV}$ as $S$, then
this is trivially true, since $\overrightarrow{V}$ is the angular bisector of
$\sphericalangle SVS^{\prime}$. Thus, let $S$ and $S^{\prime}$ lie on opposite
sides of $\overleftrightarrow{OV}$ and consider the angles
$\varphi_{S}=\sphericalangle SVO$ and $\varphi_{S^{\prime}}=\sphericalangle
OVS^{\prime}$. Since $\overrightarrow{V}$ is the angle bisector of
$\sphericalangle SVS^{\prime}$, we know that the angle between
$\overrightarrow{VS}$ and $\overrightarrow{V}$ is
$1/2(\varphi_{S}+\varphi_{S^{\prime}})$. To show that $\overrightarrow{V}$ is
on the same side of $\overleftrightarrow{OV}$ as $S$, it then suffices to show
that $1/2(\varphi_{S}+\varphi_{S^{\prime}})\leq\varphi_{S}$ or equivalently
that $\varphi_{S^{\prime}}\leq\varphi_{S}$. To this end, we make use of the
hyperbolic law of cosines.

Consider the triangles $\bigtriangleup OVS$ and $\bigtriangleup OVS^{\prime}$
and note that $\varphi_{S}$ and $\varphi_{S^{\prime}}$ are the angles at $V$,
respectively. Moreover, since $S$ and $S^{\prime}$ lie on the witness circle
of $V$, we have $|\overline{VS}|=|\overline{VS^{\prime}}|$. If
$r(S^{\prime})=r(S)$, the side lengths of the triangles match and we have
$\varphi_{S}=\varphi_{S^{\prime}}$ by Equation (1). If $r(S^{\prime})<r(S)$,
i.e., if $|\overline{OS^{\prime}}|<|\overline{OS}|$, we can apply Lemma 2.1 to
conclude that $\varphi_{S^{\prime}}<\varphi_{S}$.

Figure 8: Illustration of the proof of Corollary 4.12. Since $\sphericalangle
IVS^{\prime}<\sphericalangle IVS^{\prime\prime}$ the distance from $I$ to
$S^{\prime}$ is smaller than the one to $S^{\prime\prime}$.

As a corollary of the above lemma, we can conclude that before the sweep
circle radius reaches the far point $V^{\prime}$ of $V$, there are two
intersections whose distance to the sites of the intersecting beach ellipses
is smaller than two the third site.

######  Corollary 4.12.

Let $V\in\mathcal{V}$ be a Voronoi vertex with far point $V^{\prime}$ and
incidence tuple $(S_{1},S_{2},S_{3})$. Further, let
$(S,S^{\prime},S^{\prime\prime})\in\\{(S_{1},S_{2},S_{3}),(S_{2},S_{3},S_{1})\\}$
and consider the intersection $I\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S^{\prime}$ with $I=V$
at $\hat{r}=r(V^{\prime})$. Then,
$|\overline{IS^{\prime\prime}}|>|\overline{IS}|=|\overline{IS^{\prime}}|$ for
$\hat{r}<r(V^{\prime})$.

######  Proof 4.13.

Without loss of generality, assume that $\sphericalangle
S^{\prime}VS^{\prime\prime}\leq\sphericalangle S^{\prime\prime}VS$. Consider
the two triangles $\bigtriangleup IVS^{\prime}$ and $\bigtriangleup
IVS^{\prime\prime}$, as illustrated in Figure 8, and note that
$|\overline{VS^{\prime}}|=|\overline{VS^{\prime\prime}}|$, since $S^{\prime}$
and $S^{\prime\prime}$ lie on the witness circle of $V$. By Lemma 4.10, we
know that $I$ lies on the angle bisector $\overrightarrow{V}$ of
$\sphericalangle SVS^{\prime}$, meaning $I$ lies between $\overrightarrow{VS}$
and $\overrightarrow{VS^{\prime}}$ in clockwise direction around $V$. By
definition of the incidence tuple, we know that $S^{\prime\prime}$ does not
lie between $\overrightarrow{VS}$ and $\overrightarrow{VS^{\prime}}$ in
clockwise direction, meaning $\sphericalangle IVS^{\prime}<\sphericalangle
IVS^{\prime\prime}$. Consequently, we can apply Lemma 2.1 to conclude that
$|\overline{IS}|=|\overline{IS^{\prime}}|<|\overline{IS^{\prime\prime}}|$.

Finally, we investigate how we can use the beach ellipse intersections to
predict circle events and how to distinguish between true and false ones (see
Section 3.2). Predicting the event is straightforward, as we only need to
compute the intersection $P$ of the two bisectors corresponding to two beach
ellipse intersections that are consecutive222We argue in the proof of Lemma
4.24 that it suffices to consider consecutive intersections. on the beach
curve. We note that $P$ may not exist, in which case no circle event is
predicted. If it does exist, we need to determine whether the two beach
ellipse intersections converge towards $P$ as the sweep circle expands. To
this end, let $S_{1}$ and $S_{2}$ be two sites and recall that an intersection
$I\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S_{1}\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S_{2}$ moves away from
the line through the pole and the site with the larger radius (Lemma 4.8). We
call this site the _dominant site_ of $I$. The following lemma now says that,
as the sweep circle expands, two beach ellipse intersections meet at a point
$P$ (predicting a true circle event), if $P$ and the intersections are on the
same side of the lines through the pole and the dominant sites. See Figure 9
for an illustration.

######  Lemma 4.14.

Let $S_{1},S_{2},S_{3}\in\mathcal{S}_{\leq\hat{r}}$ be distinct and let
$P\in\mathbb{H}^{2}$ lie at distance $d$ to them. Further, let $r<r(P)+d$ be
such that $I\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S_{1}\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S_{2}$ and
$I^{\prime}\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S_{2}\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S_{3}$ are distinct at
$\hat{r}=r$ and let $S$ and $S^{\prime}$ be their dominant sites,
respectively. Then, $P=I=I^{\prime}$ at $\hat{r}=r(P)+d$, if and only if $P$
and $I$ (resp. $I^{\prime}$) are on the same side of $\overleftrightarrow{OS}$
(resp. $\overleftrightarrow{OS^{\prime}}$) at $\hat{r}=r$.

######  Proof 4.15.

We give the proof for $I$ and $\overleftrightarrow{OS}$. The one for
$I^{\prime}$ and $\overleftrightarrow{OS^{\prime}}$ is analogous. Note that
the positions of the sites and thus the coordinates of $S$ and $P$ are fixed.
Consequently, $P$ is on the same side of $\overleftrightarrow{OS}$ at all
times. Moreover, by Lemma 4.8 the intersection $I$ is on the same side of
$\overleftrightarrow{OS}$ at all times. It follows that, if and only if $P$
and $I$ are on the same side of $\overleftrightarrow{OS}$ at a given sweep
circle radius, then this holds for all sweep circle radii.

When $\hat{r}=r(P)+d$, the sweep circle has equal distance to $P$ as to all
sites $S_{1},S_{2}$, and $S_{3}$, meaning $P$ lies on their beach ellipses. In
particular, we have $P=I$. Clearly, $P$ and $I$ lie on the same side of
$\overleftrightarrow{OS}$ at that point. By the above argumentation, then and
only then does the same hold at $\hat{r}=r$.

Figure 9: Illustration of the proof of Lemma 4.14. (Left) The sweep circle
(orange) has radius $\hat{r}<r(P)+d$. The point $P$ and the intersections $I$
and $I^{\prime}$ are on the same sides of $\overleftrightarrow{OS}$ and
$\overleftrightarrow{OS^{\prime}}$, respectively. (Right) The intersections
meet at $P$ when $\hat{r}=r(P)+d$.

###  4.2 Active Beach Ellipse Segments

In this section, we consider how the beach curve changes as the sweep circle
expands. We start by proving the following lemma, which characterizes when
beach ellipse intersections are active, i.e., when they are on the beach curve
$\mathcal{B}$, as depicted in Figure 10.

######  Lemma 4.16.

Let $S,T\in\mathcal{S}_{\leq\hat{r}}$ be two sites and let
$I\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$ be an intersection
of their ellipses. Then, $I\in\mathcal{B}$ if and only if there exists no site
$S^{\prime}\in\mathcal{S}_{\leq\hat{r}}$ with $S^{\prime}\neq S,T$ such that
$|\overline{S^{\prime}I}|<|\overline{SI}|=|\overline{TI}|$.

######  Proof 4.17.

We start by proving that $S^{\prime}$ does not exist if $I\in\mathcal{B}$. To
this end, we show for each $S^{\prime}\in\mathcal{S}_{\leq\hat{r}}$ with
$S^{\prime}\neq S,T$, that
$|\overline{S^{\prime}I}|\geq|\overline{SI}|=|\overline{TI}|$. Consider the
intersection $P\in\overrightarrow{OI}\cap\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S^{\prime}$. Since
$I\in\mathcal{B}$, we know that $r(I)\geq r(P)$, meaning $I$ is not inside the
beach ellipse $\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S^{\prime}$. Thus, $I$
is at least as close to the sweep circle as to $S^{\prime}$. Since the
distance between $I$ and the sweep circle is given by $\hat{r}-r(I)$, it
follows that
$|\overline{S^{\prime}I}|\geq\hat{r}-r(I)=|\overline{SI}|=|\overline{TI}|$.

Figure 10: Illustration of the proof of Lemma 4.16. The circle
$\leavevmode\hbox to6.64pt{\vbox to6.64pt{\pgfpicture\makeatletter\hbox{\hskip
3.31935pt\lower-3.31935pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{3.11935pt}{0.0pt}\pgfsys@curveto{3.11935pt}{1.7228pt}{1.7228pt}{3.11935pt}{0.0pt}{3.11935pt}\pgfsys@curveto{-1.7228pt}{3.11935pt}{-3.11935pt}{1.7228pt}{-3.11935pt}{0.0pt}\pgfsys@curveto{-3.11935pt}{-1.7228pt}{-1.7228pt}{-3.11935pt}{0.0pt}{-3.11935pt}\pgfsys@curveto{1.7228pt}{-3.11935pt}{3.11935pt}{-1.7228pt}{3.11935pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.3875pt}{0.0pt}\pgfsys@curveto{0.3875pt}{0.214pt}{0.214pt}{0.3875pt}{0.0pt}{0.3875pt}\pgfsys@curveto{-0.214pt}{0.3875pt}{-0.3875pt}{0.214pt}{-0.3875pt}{0.0pt}\pgfsys@curveto{-0.3875pt}{-0.214pt}{-0.214pt}{-0.3875pt}{0.0pt}{-0.3875pt}\pgfsys@curveto{0.214pt}{-0.3875pt}{0.3875pt}{-0.214pt}{0.3875pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\hskip 0.75ptI$
contains all points that lie at equal distance to $I$ as $S$ and $T$. Note
that this circle is tangent to the sweep circle (orange). (Left) The
intersection $I$ is on the beach curve (bold), since $S$ and $T$ are closer to
$I$ than $S^{\prime}$. (Right) The intersection $I$ is not on the beach curve,
since $S^{\prime}$ is closer to $I$ than $S$ and $T$

It remains to consider the case where $I\notin\mathcal{B}$. Then, there exists
a beach ellipse segment of another site $S^{\prime}\neq S,T$ that is active at
angular coordinate $\varphi(I)$. That is, there is a point
$P=\overrightarrow{OI}\cap\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S^{\prime}$ such that
$r(I)<r(P)$. It follows that $I$ is inside of $\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S^{\prime}$, meaning
$I$ is closer to $S^{\prime}$ than to the sweep circle. We can conclude that
$|\overline{S^{\prime}I}|<\hat{r}-r(I)=|\overline{SI}|=|\overline{TI}|$.

With the above lemma, we are now ready to investigate how changes to the beach
curve are related to the events in the queue $\mathcal{Q}$. Consider the tuple
$\mathcal{\bar{Q}}$, that contains all site events and all true circle events
(see Section 3.2). Recall that $V^{\prime}$ denotes the far point of a Voronoi
vertex $V\in\mathcal{V}$, i.e., the point with the maximum radial coordinate
among points on the witness circle of $V$. Then,
$\mathcal{\bar{Q}}=(r_{0},r_{1},\dots,r_{k},r_{k+1})$ contains the radii
$r_{0}=0$, $r_{k+1}=\infty$ and all radii $\\{r(S)\mid
S\in\mathcal{S}\\}\cup\\{r(V^{\prime})\mid V\in\mathcal{V}\\}$ in ascending
order inbetween. We note that $\mathcal{\bar{Q}}$ is different from
$\mathcal{Q}$, since the latter also contains structure events and may contain
scheduled circle events that are later canceled, e.g., when a site is detected
within the corresponding witness circle.

For two sites $S,T\in\mathcal{S}_{\leq\hat{r}}$, we say that a point
$P\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$ _enters the beach
curve at radius $r$_, if there is an $\varepsilon>0$ such that
$P\notin\mathcal{B}$ for $\hat{r}\in[r-\varepsilon,r)$ and $P\in\mathcal{B}$
when $\hat{r}=r$. Analogously, we say that $P\in\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$ _leaves the beach
curve at radius_ $r$ if $P\in\mathcal{B}$ when $\hat{r}=r$ and there is an
$\varepsilon>0$ such that $P\notin\mathcal{B}$ for
$\hat{r}\in(r,r+\varepsilon]$. In the following, we show that no beach ellipse
intersection enters or leaves the beach curve between two events in
$\mathcal{\bar{Q}}$.

######  Lemma 4.18.

Let $\mathcal{\bar{Q}}$ be the tuple of site events and true circle events and
let $r_{i},r_{j}\in\mathcal{\bar{Q}}$ be two consecutive events. Then, for all
$\hat{r}\in(r_{i},r_{j})$ no beach ellipse intersection enters the beach
curve.

######  Proof 4.19.

Let $S,T$ be two sites and let $I\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$ be an intersection
of their ellipses. For the sake of contradiction, assume that there exists an
$r\in(r_{i},r_{j})$ such that $I$ enters the beach curve at $r$. Note that no
site event occurs in $(r_{i},r_{j})$, since this would contradict the
construction of $\mathcal{\bar{Q}}$. Consequently, if $I$ is on the beach
curve at $\hat{r}=r$, we know that $I$ is contained in the sweep circle for
all $\hat{r}\in(r_{i},r_{j})$. By Lemma 4.16 we know that $I$ not being on the
beach curve before $\hat{r}=r$ implies the existence of at least one site
$S^{\prime}\neq S,T$, such that
$|\overline{S^{\prime}I}|<|\overline{SI}|=|\overline{TI}|$. In particular, we
choose $S^{\prime}$ to be the one that remains active the longest at angular
coordinate $\varphi(I)$ as the sweep circle expands beyond $r_{i}$. Since $I$
is on the beach curve at $\hat{r}=r$, we also know that
$|\overline{S^{\prime}I}|\geq|\overline{SI}|=|\overline{TI}|$ at that moment
(again Lemma 4.16). Thus, as $I$ moves along the bisector $S\\!\perp\\!T$,
there exists an $r^{\prime}\in(r_{i},r]$ such that
$|\overline{S^{\prime}I}|=|\overline{SI}|=|\overline{TI}|$ (Lemma 2.3). Then,
$I$ is the center of an empty circle (as otherwise there would be yet another
site that is longer active than $S^{\prime}$, contradicting the choice of
$S^{\prime}$) and thus lies on a Voronoi vertex $V\in\mathcal{V}$. However,
this would imply that $r^{\prime}\in(r_{i},r_{j})$ is the radius of the far
point of $V$, which again contradicts the construction of $\mathcal{\bar{Q}}$.

Note that if no intersections enter the beach curve between events in
$\mathcal{\bar{Q}}$, then also no beach ellipse segments can become active
then. Moreover, no segments become active during a circle event either, as
only two intersections are merged into one there. We can conclude the
following lemma, which is the hyperbolic sweep circle counterpart of [10,
Lemma 7.6] in the Euclidean sweep line version.

######  Lemma 4.20.

The only way in which a new beach ellipse segment can become active is through
a site event.

We continue by investigating how beach ellipse segments disappear from the
beach curve. Analogous to the proof of Lemma 4.18, we can prove that no beach
ellipse intersection leaves the beach curve between two events in
$\mathcal{\bar{Q}}$.

######  Lemma 4.21.

Let $\mathcal{\bar{Q}}$ be the tuple of site events and true circle events and
let $r_{i},r_{j}\in\mathcal{\bar{Q}}$ be two consecutive events. Then, for all
$\hat{r}\in(r_{i},r_{j})$ no beach ellipse intersection leaves the beach
curve.

######  Proof 4.22.

Consider two sites $S,T$, let $I\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}T$ be an intersection
of their ellipses, and assume for the sake of contradiction that there exists
an $r\in(r_{i},r_{j})$ such that $I$ leaves the beach curve at $r$. That is,
there exists an $\varepsilon>0$, such that $I$ is on the beach curve until
$\hat{r}=r$ and is no longer on the beach curve for
$\hat{r}\in(r,r+\varepsilon)$. By Lemma 4.16, it follows that for all sites
$S^{\prime}\neq S,T$ we have
$|\overline{S^{\prime}I}|\geq|\overline{SI}|=|\overline{TI}|$ at $\hat{r}=r$,
but at least one of them is closer to $I$ than
$|\overline{SI}|=|\overline{TI}|$ afterwards. Let $S^{\prime\prime}$ be the
one for which this happens first. That is, for this site we have
$|\overline{S^{\prime\prime}I}|\geq|\overline{SI}|=|\overline{TI}|$ at
$\hat{r}=r$ and
$|\overline{S^{\prime\prime}I}|<|\overline{SI}|=|\overline{ST}|$ afterwards.
By Lemma 2.3, we know that when $I$ moves along the bisector $S\\!\perp\\!T$
as the sweep circle expands, there exists a radius
$r^{\prime}\in[r,r+\varepsilon)$ such that
$|\overline{S^{\prime\prime}I}|=|\overline{SI}|=|\overline{TI}|$ when
$\hat{r}=r^{\prime}$. As by the choice of $S^{\prime\prime}$, no other site is
closer to $I$ than $S^{\prime\prime},S$, and $T$, we know that $I$ is the
center of an empty circle and thus lies on a Voronoi vertex $V\in\mathcal{V}$.
However, this implies that $r^{\prime}\in(r_{i},r_{j})$ is the radius of the
far point of $V$, which contradicts the construction of $\mathcal{\bar{Q}}$.

Again, note that if no intersections can leave the beach curve between events
in $\mathcal{\bar{Q}}$, then also no beach ellipse segment can become inactive
then. Moreover, no segments become inactive during a site event, since we only
insert two intersections consecutively on the beach curve there. As a result,
we obtain the following lemma, which is the hyperbolic equivalent of [10,
Lemma 7.7] in the Euclidean sweep line approach.

######  Lemma 4.23.

The only way in which an active beach ellipse segment can become inactive is
through a circle event.

###  4.3 Voronoi Vertices

It remains to prove that all Voronoi vertices are actually found by means of
circle events. To simplify this proof, we make the assumption that at most
three sites are incident to a Voronoi vertex $V\in\mathcal{V}$, meaning no
more than three sites lie on its witness circle. If this assumption does not
hold, the algorithm may produce duplicate Voronoi vertices, which need to be
merged in a post-processing step. The following lemma is the analog of [10,
Lemma 7.8] in the Euclidean version.

######  Lemma 4.24.

Every Voronoi vertex is detected by means of a circle event.

######  Proof 4.25.

Let $V\in\mathcal{V}$ be a Voronoi vertex, let $V^{\prime}$ be its far point,
and let $(S_{1},S_{2},S_{3})$ be the incidence tuple of $V$. Further, let
$r\in\mathcal{\bar{Q}}$ be the predecessor of $r(V^{\prime})$ in
$\mathcal{\bar{Q}}$. To show that $V$ is detected by means of a circle event,
we prove that for all sweep circle radii $\hat{r}\in[r,r(V^{\prime}))$ there
are beach ellipse intersections $I_{12}\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S_{1}\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S_{2}$ and
$I_{23}\in\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S_{2}\cap\leavevmode\hbox
to5.56pt{\vbox to6.97pt{\pgfpicture\makeatletter\hbox{\hskip
2.77756pt\lower-3.4843pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S_{3}$ that are
consecutive on the beach curve $\mathcal{B}$. Then, it follows that the
corresponding circle event is in the event queue $\mathcal{Q}$ and the Voronoi
vertex is detected at $\hat{r}=r(V^{\prime})$.

We start by showing that $I_{12},I_{23}\in\mathcal{B}$ for
$\hat{r}\in[r,r(V^{\prime}))$. In particular, we give the proof for $I_{12}$,
as the one for $I_{23}$ is analogous. For the sake of contradiction, assume
that there exists an $r^{\prime}\in[r,r(V^{\prime}))$ such that
$I_{12}\notin\mathcal{B}$ when $\hat{r}=r^{\prime}$. By Lemma 4.4, $I_{12}$
exists, so the only way for it _not_ to be on the beach curve is that there
exists another site $S\neq S_{1},S_{2}$ such that
$|\overline{SI_{12}}|<|\overline{S_{1}I_{12}}|=|\overline{S_{2}I_{12}}|$
(Lemma 4.16). Moreover, by Corollary 4.12 we have
$|\overline{S_{3}I_{12}}|>|\overline{S_{1}I_{12}}|=|\overline{S_{1}I_{12}}|$.
It follows that $S\neq S_{3}$. We now show that the site $S$ that is distinct
from $S_{1},S_{2}$, and $S_{3}$ cannot exist.

By Lemma 4.18 we know that $I_{12}$ does not enter the beach curve until at
least $\hat{r}=r(V^{\prime})$. Now first consider the case where $I_{12}$
enters the beach curve exactly at $\hat{r}=r(V^{\prime})$, i.e., exactly when
$I_{12}=V$. This means that
$|\overline{SI_{12}}|\geq|\overline{S_{1}I_{12}}|=|\overline{S_{2}I_{12}}|$ at
this point (Lemma 4.16). In particular, we have
$|\overline{SI_{12}}|=|\overline{S_{1}I_{12}}|=|\overline{S_{2}I_{12}}|$ then,
as by Lemma 2.3 there exists a point at which we have equality but this point
does not occur before $\hat{r}=r(V^{\prime})$. It follows that besides
$S_{1},S_{2}$, and $S_{3}$, the site $S$ is on the witness circle of $V$,
contradicting our assumption that no more than three sites do. Now consider
the case where $I_{12}$ does not enter the beach curve at
$\hat{r}=r(V^{\prime})$, i.e., when $I_{12}=V$. By Lemma 4.16, we know that
$|\overline{SI_{12}}|<|\overline{S_{1}I_{12}}|$, i.e,
$|\overline{SV}|<|\overline{S_{1}V}|$, which means that $S$ is contained in
the witness circle of $V$, contradicting the assumption that $V$ is a Voronoi
vertex. Since both cases lead to a contradiction, we can conclude that
$I_{12}\in\mathcal{B}$ for all $\hat{r}\in[r,r(V^{\prime}))$.

It remains to show that $I_{12}$ and $I_{23}$ are also consecutive on
$\mathcal{B}$ for $\hat{r}\in[r,r(V^{\prime}))$. First note that any
intersection that were to lie between $I_{12}$ and $I_{23}$ cannot span beyond
these two intersections, as this would contradict the fact that
$I_{12},I_{23}\in\mathcal{B}$, which we just proved. It follows that if
$I_{12},I_{23}$ are not consecutive on $\mathcal{B}$, then there are at least
two intersections $I$ and $I^{\prime}$ between them that belong to the same
active segment $\mathcal{A}$, which is part of the beach ellipse of another
site $S$. Since none of the intersections $I_{12},I_{23},I$, and $I^{\prime}$
leave $\mathcal{B}$ until at least $\hat{r}=r(V^{\prime})$ (Lemma 4.21), it
follows that $I$ and $I^{\prime}$ stay between $I_{12}$ and $I_{23}$ until
$\hat{r}=r(V^{\prime})$, which is when $I_{12}$ and $I_{23}$ meet at $V$.
Then, $V=I_{12}=I_{23}=I=I^{\prime}$. Now note that only three intersections
of the beach ellipses of the sites $S_{1},S_{2}$, and $S_{3}$ meet at $V$,
since the two beach ellipse intersections of a pair of them travel in opposite
directions on the perpendicular bisector, only one of which leads to $V$
(Lemma 4.8). Thus, at least one of $I$ and $I^{\prime}$ belongs to a beach
ellipse $\leavevmode\hbox to5.56pt{\vbox
to6.97pt{\pgfpicture\makeatletter\hbox{\hskip 2.77756pt\lower-3.4843pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}{{{}}
{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.46227pt}{3.2843pt}\pgfsys@curveto{0.48473pt}{3.71953pt}{-0.96239pt}{2.60193pt}{-1.76997pt}{0.78804pt}\pgfsys@curveto{-2.57756pt}{-1.02585pt}{-2.4398pt}{-2.84908pt}{-1.46227pt}{-3.2843pt}\pgfsys@curveto{-0.48473pt}{-3.71953pt}{0.96239pt}{-2.60193pt}{1.76997pt}{-0.78804pt}\pgfsys@curveto{2.57756pt}{1.02585pt}{2.4398pt}{2.84908pt}{1.46227pt}{3.2843pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@moveto{1.18402pt}{1.93748pt}\pgfsys@curveto{1.18402pt}{2.17528pt}{0.99126pt}{2.36804pt}{0.75346pt}{2.36804pt}\pgfsys@curveto{0.51567pt}{2.36804pt}{0.3229pt}{2.17528pt}{0.3229pt}{1.93748pt}\pgfsys@curveto{0.3229pt}{1.69969pt}{0.51567pt}{1.50693pt}{0.75346pt}{1.50693pt}\pgfsys@curveto{0.99126pt}{1.50693pt}{1.18402pt}{1.69969pt}{1.18402pt}{1.93748pt}\pgfsys@closepath\pgfsys@moveto{0.75346pt}{1.93748pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}S$ with $S\neq
S_{1},S_{2},S_{3}$. It follows that a fourth site lies on the witness circle
of $V$, contradicting the assumption that no more than three do.

###  4.4 Complexity

To conclude the proof of Theorem 4.1, it remains to show that the algorithm
takes time $\mathcal{O}(n\log(n))$ to compute the Voronoi diagram of $n$
sites. Initially, all site events need to be scheduled, meaning the sites have
to be sorted by their radii, which takes time $\mathcal{O}(n\log(n))$. The
running time of the remainder of the algorithm then depends on the complexity
of the diagram, i.e., the number of Voronoi vertices and edges. It was
previously shown that this complexity is $\mathcal{O}(n)$, by examining
different models: the Poincare disk model [6, Consequence of Proposition 2],
the Poincaré half-plane model [9, Theorem 18.5.1] and the Klein disk model
[21, Theorem 1]. Of course, it is no surprise that all came to the same
conclusion, since the different models represent different ways to address
points in the same space.

Clearly, there are exactly $n$ site events and the number of true circle
events is bounded by the number of Voronoi vertices, which is
$\mathcal{O}(n)$. As each event is processed, at most a constant number of
circle events are scheduled and as the algorithm proceeds the number of
canceled events cannot be larger. Moreover, since each intersection can
contribute at most one structure event, it follows that the total number of
processed events is $\mathcal{O}(n)$.

It remains to show that we can handle an event in time $\mathcal{O}(\log(n))$.
Since the queue contains $\mathcal{O}(n)$ events, inserting and removing
elements from the queue, takes time $\mathcal{O}(\log(n))$. Regarding updating
the beach curve data structure, recall that two beach ellipses intersect at
most two times (Lemma 4.4) and note that, consequently, at most two
intersections are on the same edge of the Voronoi diagram at all times. It
follows that the number of elements in the beach curve is at most
$\mathcal{O}(n)$ at all times, meaning insertions and deletions take at most
$\mathcal{O}(\log(n))$ time. All other operations, like inserting vertices to
the diagram, marking bisectors incident to the vertices, and predicting new
circle and structure events, take constant time.

##  5 Outlook

We present the first algorithm for computing Voronoi diagrams natively in the
polar-coordinate model of the two-dimensional hyperbolic plane. We note that
the distance function in this model generalizes nicely to higher dimensions,
as only the computation of the angular distance between two points changes
(one has to compute the central angle). Consequently, we believe that the
hyperbolic sweep circle approach can be extended to higher dimensions.
Furthermore, it would be interesting to extend the method to allow for
computations of higher-order Voronoi diagrams, as they are useful in the
context of nearest-neighbor queries.

A more direct application of our algorithm is the efficient computation of the
hyperbolic counterpart to Euclidean minimum spanning trees. To the best of our
knowledge _hyperbolic random minimum spanning trees_ have not been studied
before, but may prove useful as the tree equivalent to the aforementioned
hyperbolic random graph model [16]. Analogous to the Euclidean version, the
hyperbolic minimum spanning tree is a subgraph of the hyperbolic Delaunay
complex of a given set of sites, meaning it can be computed in time
$\mathcal{O}(n\log(n))$ using our approach. Consequently, it would be
interesting to implement our hyperbolic sweep circle method in order to
generate and investigate trees in the hyperbolic plane.

## References

  * [1] Gregorio Alanis-Lobato, Pablo Mier, and Miguel Andrade-Navarro.  The latent geometry of the human protein interaction network.  Bioinformatics, 34:2826–2834, 2018.  doi:10.1093/bioinformatics/bty206.
  * [2] Marshall Bern and David Eppstein.  Optimal Möbius Transformations for Information Visualization and Meshing.  In Algorithms and Data Structures (WADS), pages 14–25, 2001.  doi:10.1007/3-540-44634-6_3.
  * [3] Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, and Maximilian Katzmann.  Solving vertex cover in polynomial time on hyperbolic random graphs.  Theory of Computing Systems, 2021.  doi:10.1007/s00224-021-10062-9.
  * [4] Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, and Marianne Thieffry.  Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry.  In International Colloquium on Automata, Languages, and Programming (ICALP), pages 20:1–20:14, 2018.  doi:10.4230/LIPIcs.ICALP.2018.20.
  * [5] Martin Bock, Amit Kumar Tyagi, Jan-Ulrich Kreft, and Wolfgang Alt.  Generalized Voronoi Tessellation as a Model of Two-dimensional Cell Tissue Dynamics.  Bulletin of Mathematical Biology, 72(7):1696–1731, 2010.  doi:10.1007/s11538-009-9498-3.
  * [6] Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud.  Hyperbolic Delaunay complexes and Voronoi diagrams made practical.  Journal of Computational Geometry, 5:56–85, 2014.  doi:10.20382/JOCG.V5I1A4.
  * [7] Marian Boguna, Fragkiskos Papadopoulos, and Dmitri Krioukov.  Sustaining the Internet with Hyperbolic Mapping.  Nature Communications, 1(1):62, 2010.  doi:10.1038/ncomms1063.
  * [8] Jean-Daniel Boissonnat, André Cérézo, Olivier Devillers, and Monique Teillaud.  Output-sensitive construction of the Delaunay triangulation of points lying in two planes.  International Journal of Computational Geometry and Applications, 06(01):1–14, 1996.  doi:10.1142/S0218195996000022.
  * [9] Jean-Daniel Boissonnat and Mariette Yvinec.  Non-Euclidean metrics.  Cambridge University Press, 1998.  doi:10.1017/CBO9781139172998.025.
  * [10] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.  Computational Geometry: Algorithms and Applications.  Springer, 2008.
  * [11] David S. Ebert, F. Kenton Musgrave, Darwyn Peachey, Ken Perlin, and Steven Worley.  Texturing and Modeling: A Procedural Approach.  Elsevier Science, 2002.
  * [12] Steven Fortune.  A sweepline algorithm for Voronoi diagrams.  In Symposium on Computational Geometry (SoCG), page 313–322, 1986.  doi:10.1145/10515.10549.
  * [13] Guillermo García-Pérez, Marián Boguñá, Antoine Allard, and M. Serrano.  The hidden hyperbolic geometry of international trade: World trade atlas 1870–2013.  Scientific Reports, 6:33441, 2016.  doi:10.1038/srep33441.
  * [14] Santiago Garrido, Luis Moreno, Mohamed Abderrahim, and Fernando Martin.  Path Planning for Mobile Robot Navigation using Voronoi Diagram and Fast Marching.  In 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2376–2381, 2006.  doi:10.1109/IROS.2006.282649.
  * [15] Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter.  Random hyperbolic graphs: Degree sequence and clustering.  In International Colloquium on Automata, Languages, and Programming (ICALP), page 573–585, 2012.  doi:10.1007/978-3-642-31585-5_51.
  * [16] Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá.  Hyperbolic geometry of complex networks.  Physical Review E, 82:036106, 2010.  doi:10.1103/PhysRevE.82.036106.
  * [17] Anton Krohmer.  Structures & algorithms in hyperbolic random graphs.  Dissertation, Universität Potsdam, 2016.
  * [18] Richard G. Lyons.  Sum of two sinusoids.  2011\.  URL: https://dspguru.com/files/Sum_of_Two_Sinusoids.pdf.
  * [19] Tobias Müller and Merlijn Staps.  The diameter of kpkvb random graphs.  Advances in Applied Probability, 51(2):358–377, 2019.  doi:10.1017/apr.2019.23.
  * [20] Frank Nielsen.  On Voronoi Diagrams on the Information-Geometric Cauchy Manifolds.  Entropy, 22(7), 2020.  doi:10.3390/e22070713.
  * [21] Frank Nielsen and Richard Nock.  Hyperbolic Voronoi Diagrams Made Easy.  In International Conference on Computational Science and Its Applications (ICCSA), page 74–80, 2010.  doi:10.1109/ICCSA.2010.37.
  * [22] Frank Nielsen and Richard Nock.  Visualizing Hyperbolic Voronoi Diagrams.  In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, page 90–91, 2014.  doi:10.1145/2582112.2595647.
  * [23] Zahra Nilforoushan and Ali Mohades.  Hyperbolic Voronoi Diagram.  In Computational Science and Its Applications (ICCSA), page 735–742, 2006.  doi:10.1007/11751649_81.
  * [24] Kensuke Onishi and Nobuki Takayama.  Construction of Voronoi Diagram on the Upper Half-Plane.  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 79:533–539, 1996.
  * [25] Arlan Ramsay and Robert D. Richtmyer.  Introduction to Hyperbolic Geometry.  Springer, 1995.  doi:10.1007/978-1-4757-5585-5.
  * [26] Michael Ian Shamos.  Computational Geometry.  Dissertation, Department of Computer Science, Yale University, 1977.
  * [27] Toshihiro Tanuma, Hiroshi Imai, and Sonoko Moriyama.  Revisiting Hyperbolic Voronoi Diagrams in Two and Higher Dimensions from Theoretical, Applied and Generalized Viewpoints, pages 1–30.  Springer Berlin Heidelberg, 2011.  doi:10.1007/978-3-642-25249-5_1.
  * [28] Shi-Qing Xin, Xiaoning Wang, Jiazhi Xia, Wolfgang Mueller-Wittig, Guo-Jin Wang, and Ying He.  Parallel computing 2D Voronoi diagrams using untransformed sweepcircles.  Computer-Aided Design, 45(2):483–493, 2013.  doi:10.1016/j.cad.2012.10.031.