Department of Information and Computing Sciences, Utrecht University, the
Netherlands and Department of Computer Science, Tulane University, New
Orleans, United States of America and https://www.uu.nl/staff/MLoffler/Profile
<EMAIL_ADDRESS>Department of Information and Computing Sciences, Utrecht
University, the Netherlands and Department of Mathematics and Computer
Science, TU Eindhoven, the Netherlands<EMAIL_ADDRESS>Department of
Information and Computing Sciences, Utrecht University, the Netherlands
<EMAIL_ADDRESS>Department de Matemàtiques, Universitat Politècnica de
Catalunya, Spain and http://dccg.upc.edu/people/rodrigo/
<EMAIL_ADDRESS>Partially funded by MICINN through project
PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033. Maarten Löffler, Tim
Ophelders, Rodrigo I. Silveira, Frank Staals [100]Theory of computation
Computational Geometry

# Shortest Paths in Portalgons

Maarten Löffler  Tim Ophelders  Frank Staals  Rodrigo I. Silveira

###### Abstract

Any surface that is intrinsically polyhedral can be represented by a
collection of simple polygons (_fragments_), glued along pairs of equally long
oriented edges, where each fragment is endowed with the geodesic metric
arising from its Euclidean metric. We refer to such a representation as a
_portalgon_ , and we call two portalgons equivalent if the surfaces they
represent are isometric.

We analyze the complexity of shortest paths. We call a fragment _happy_ if any
shortest path on the portalgon visits it at most a constant number of times. A
portalgon is happy if all of its fragments are happy. We present an efficient
algorithm to compute shortest paths on happy portalgons.

The number of times that a shortest path visits a fragment is unbounded in
general. We contrast this by showing that the intrinsic Delaunay triangulation
of any polyhedral surface corresponds to a happy portalgon. Since computing
the intrinsic Delaunay triangulation may be inefficient, we provide an
efficient algorithm to compute happy portalgons for a restricted class of
portalgons.

###### keywords:

Polyhedral surfaces, shortest paths, geodesic distance, Delaunay triangulation

##  1 Introduction

Figure 1: Examples of portalgons. Arrows of the same color represent portals
that are identified with each other. (a) A portalgon that represents a polygon
with a hole. (b) A portalgon that represents the surface of a bottomless
pyramid. (c) A portalgon that represents the surface of a cylinder. (d) A
portalgon that represents a Möbius strip, a non-orientable surface.

We define a portalgon $\mathcal{P}$ to be a collection of simple polygons
(fragments) with some pairs of edges identified, see Figure 1. When we stitch
together all fragments of a portalgon we obtain a two-dimensional surface
$\Sigma$, whose intrinsic metric is polyhedral [8, 19]. Note that $\Sigma$ is
not necessarily embeddable in $\mathbb{R}^{3}$ with flat faces or without
self-intersections, and not necessarily orientable. We say that $\mathcal{P}$
is a representation of $\Sigma$; crucially, the same surface may in principle
have many different representations. Portalgons can be seen as a
generalization of simple polygons, polygons with holes, polyhedral surfaces,
and even developable surfaces.

We are interested in the computational complexity of computing shortest paths
on portalgons. In particular, we analyze the shortest path map
$\operatorname{SPM}(s)$; a representation of all shortest paths from a source
point $s$ to all other points in the portalgon. Our main insights are:

  * •

The complexity of a shortest path on a surface $\Sigma$, represented by a
given portalgon $\mathcal{P}$, may be unbounded in terms of the combinatorial
properties of $\Sigma$ and $\mathcal{P}$.

  * •

The complexity of a shortest path depends on a parameter of the particular
portalgon $\mathcal{P}$ representing the surface that we refer to as its
_happiness_ $h$. In particular, we show that the maximum complexity of a
shortest path is $\Theta(n+hm)$, where $n$ is the total number of vertices in
the portalgon, $m\leq n$ is the number of portals.

  * •

Given a source point in $\mathcal{P}$, the complexity of its shortest path map
is $O(n^{2}h)$. Moreover, if $\mathcal{P}$ is triangulated, it can be computed
in $O(\lambda_{4}(k)\log^{2}k)$ time, where $k$ is the output complexity, and
$\lambda_{4}(k)$ the length of an order-4 Davenport-Schinzel sequence on $k$
symbols.

  * •

Every surface with a polyhedral intrinsic metric admits a representation as a
portalgon where the happiness $h$ is constant. Specifically, one such
representation is given by its intrinsic Delaunay triangulation. In such
portalgons shortest paths have complexity $O(n)$.

  * •

Since the intrinsic Delaunay triangulation is not easy to compute, we
investigate the problem of transforming a given portalgon of happiness $h$
into one with constant happiness. We present an algorithm to do so in
$O(n+\log h)$ time, for a restricted class of portalgons. The question of how
to compute such a good representation, in general, remains open.

Figure 2:  (a) A portalgon where a shortest path between $s$ and $t$ (dashed)
has unbounded complexity. (b) A different representation of the same surface
where the path has constant complexity.

###  1.1 Comparison to related work

Shortest paths have been studied in many different geometric settings, such as
simple polygons, polygonal domains, terrains, surfaces, and polyhedra (see
e.g. [6, 12, 14, 24]; refer to [21] for a comprehensive survey). The efficient
_computation_ of shortest paths is a fundamental problem in computational
geometry [20, 23, 13, 6, 28, 27]. When the environment is a simple polygon the
situation is well understood [13, 12]. For polygons with holes, efficient
solutions have also been known for quite a while [14], recently culminating in
an optimal $O(n+k\log k)$ time algorithm, where $n$ is the total number of
vertices of the polygon, and $k$ the number of holes [27]. For more complex
environments, like the surface of a convex polyhedron, several algorithms have
been developed [6, 22, 29], and even implemented [15, 16]. However, for more
general surfaces the situation is less well understood.

Portalgons generalize many of the geometric settings studied before. Hence,
our goal is to unify existing shortest paths results. To the best of our
knowledge, this has not been attempted before, even though several questions
closely related to the ones addressed in this work were posed as open problems
in a blog post almost two decades ago [10]. Instead, portalgons are a rather
unexplored concept which, though it has been long adopted into popular culture
[7, 9, 26], have only been studied from a computational point of view in the
context of annular ray shooting by Erickson and Nayyeri [11].

When measuring the complexity of a shortest path, we can distinguish between
its intrinsic complexity, and complexity caused by the representation of the
underlying surface. For example, a shortest path $\pi$ on a convex polyhedron
$\Sigma$ in $\mathbb{R}^{3}$ with $n$ vertices, may cross (and thus bend) at
$O(n)$ edges. Hence, a description of $\pi$ on $\Sigma$ has complexity $O(n)$.
However, it is known that any convex polyhedron in $\mathbb{R}^{3}$ can be
unfolded into a simple planar polygon $P_{\Sigma}$, and in such a way that a
shortest path $\pi$ corresponds to a line segment in $P_{\Sigma}$ [1, 2, 6].
Hence, $\pi$ actually has a constant complexity description in $P_{\Sigma}$.
It is easy to see that some portalgons may have shortest paths of unbounded
complexity; as illustrated in Figure 2(a). This unbounded complexity, however,
is completely caused by the representation, and indeed there is another
equivalent portalgon without this behavior (Figure 2(b)). We introduce a
parameter that explicitly measures the potential for shortest paths to have
high complexity, which we call happiness—refer to Section 2 for a formal
definition.

In Section 3, we analyze the complexity of shortest paths in terms of the
happiness. Our first main result is that, if we have a portalgon with $n$
vertices and happiness $h$, then the complexity of its shortest path map from
a given source point is $O(n^{2}h)$. Moreover, we show that, for triangulated
portalgons, it can be computed in an output-sensitive fashion: if $k$ is the
complexity of the shortest path map, then it can be computed in
$O(\lambda_{4}(k)\log^{2}k)$ time.

It is worth noting that our analysis of the shortest path map has similarities
with techniques used to compute shortest paths on polyhedral surfaces, most
notably [6, 22]. However, the fact that portalgons are more general implies
important differences with previous methods. We need to handle surfaces of
non-zero genus (e.g., see Figure 3),

Figure 3: (a) A portalgon representing a flat torus. (b) Interestingly, a flat
torus can be embedded isometrically in $\mathbb{R}^{3}$; however, the
resulting embedding has very high complexity [5, 17] (image from
https://www.imaginary.org/es/node/2375).

while Chen and Han [6] require genus zero to compute the map in the interior
of triangles (see the proof of their Theorem 4). Moreover, $\Sigma$ may be
non-embeddable in Euclidean space with flat triangles. Another difference is
that shortest paths in portalgons can cross the same portal edge multiple
times, something that is often (explicitly or implicitly) assumed to be
impossible in algorithms for polyhedral surfaces (e.g., in [22]).

The fact that the complexity of the shortest path map can be upper bounded by
a function of the happiness, leads to the following natural question: for a
given surface $\Sigma$, can it always be represented by a portalgon
$\mathcal{P}$ with bounded happiness? In Section 4, we prove that the answer
to this question is “yes”. In particular, our second main result is that for
any portalgon, its intrinsic Delaunay triangulation [4] has constant
happiness.

In turn, this then leads to another natural question: given a surface
$\Sigma$, can we actually efficiently compute a portalgon representing it that
has bounded, preferably constant, happiness? Clearly, the answer to this
question depends on how $\Sigma$ is represented. When $\Sigma$ is given as a
portalgon $\mathcal{P}$, possibly with unbounded happiness, this question then
corresponds to the problem of transforming $\mathcal{P}$ into an equivalent
portalgon with constant happiness. This is the problem we study in Section 5.
Given the above result, the natural approach is to try to construct the
intrinstic Delaunay triangulation of $\mathcal{P}$. Unfortunately, it is
unknown if it is possible to do that efficiently (that is, with guarantees in
terms of $n$ and $h$). Our third main result shows that for a restricted class
of portalgons we can give such guarantees. In particular, if the input
portalgon has only one portal, $n$ vertices, and happiness $h$, we can
construct an equivalent portalgon that has constant happiness in $O(n+\log h)$
time.

##  2 Definitions and observations

##### Portalgons.

We define a _portalgon_ $\mathcal{P}$ to be a pair $(\mathcal{F},P)$, where
$\mathcal{F}$ is a collection of simple polygons, called _fragments_ , and $P$
is a collection of portals. A _portal_ is an unordered pair
$e=({e^{-}},{e^{+}})$ of directed, distinct, equal length, edges from some
fragment(s) of $\mathcal{F}$. We refer to ${e^{-}}$ and ${e^{+}}$ as _portal
edges_ , see Figure 1(c), and require that each portal edge appears in one
portal. If ${p^{-}}$ is a point on ${e^{-}}$, then ${p^{+}}$ will denote the
corresponding point on ${e^{+}}$.

Let $n$ be the total number of vertices in the fragments of $\mathcal{P}$, and
let $m$ be the number of portal edges; the number of portals is $m/2$. Note
that $m\leq n$. We denote the number of vertices and the number of portal
edges in a fragment $F\in\mathcal{F}$ by $n_{F}$ and $m_{F}$, respectively.

If we “glue” the edges of the fragments along their common portal edges, then
the portalgon $\mathcal{P}$ describes a surface (2-manifold with boundary)
$\Sigma=\Sigma(\mathcal{P})$, see Figure 1. Specifically, $\Sigma$ is the
space obtained from $\mathcal{P}$ by taking the collection $\mathcal{F}$ and
identifying corresponding pairs of points on portal edges. We can write
$\Sigma$ as a quotient space $(\bigcup_{F\in\mathcal{F}}F)/\sim$, where $\sim$
is an equivalence relation that glues corresponding portal edges ${e^{-}}$ and
${e^{+}}$.

##### Fragment Graph.

A portalgon $\mathcal{P}=(\mathcal{F},P)$ induces a (multi)graph that we refer
to as the _fragment graph_ $G$ of $\mathcal{P}$ (see Figure 4). Each fragment
$F\in\mathcal{F}$ is a node in $G$, and there is a link between $F_{1}$ and
$F_{2}$ in $G$ if and only if there is a portal $e$ with ${e^{-}}$ in $F_{1}$
and ${e^{+}}$ in $F_{2}$, or vice versa. Note there may be multiple portals
connecting $F_{1}$ and $F_{2}$.

Figure 4: The fragment graph of a portalgon with four fragments and five
portals.

##### Paths and shortest paths.

A path $\pi$ from $s\in\Sigma$ to $t\in\Sigma$ is a continuous function
mapping the interval $[0,1]$ to $\Sigma$, where $s=\pi(0)$ and $t=\pi(1)$. For
two points $p=\pi(a)$ and $q=\pi(b)$, we use $\pi[p,q]$ to denote the
restriction of $\pi$ to the interval $[a,b]$. The fragments of $\mathcal{P}$
split $\pi$ into a set $\Pi$ of maximal, non-empty, subpaths
$\pi_{1},..,\pi_{z}$, where (the image of) each $\pi_{i}$ is contained in a
single fragment. To be precise, for each fragment $F$, the intersection of
(the image of) $\pi$ with $F$ is a set of maximal subpaths, and $\Pi$ is the
union of those sets over all fragments $F$111Note that if $\pi$ passes through
a vertex of $\mathcal{P}$ that appears in multiple portals, $\Pi$ contains
subpaths for which the image consists of only a single point; the vertex
itself. We later restrict our attention to minimum complexity paths, which
allows us to get rid of such singleton paths. . We define the length of $\pi$
as the sum of the lengths of its subpaths, and the distance $d(s,t)$ between
$s\in\Sigma$ and $t\in\Sigma$ as the infimum of length over all paths between
$s$ and $t$. We inherit the property that $d(s,t)=0$ if and only if $s=t$ from
the metric in each fragment. It then follows that $d$ is also a metric.
Moreover, $(\Sigma,d)$ is a geodesic space.

Observe that if $\pi$ is a shortest path between $s$ and $t$, each subpath
$\pi_{i}$ is a polygonal path whose vertices are either endpoints of $\pi_{i}$
or vertices of the fragment containing $\pi_{i}$. Furthermore, when $\pi$
crosses a portal the path does not bend (otherwise we can again locally
shortcut it). It then follows that a shortest path $\pi$ is also polygonal and
can be uniquely described by an alternating sequence
$s=v_{1},E_{1},v_{2},..,E_{k},v_{k+1}=t$ of vertices ($s$, $t$, or portalgon
vertices) and sequences of portal edges crossed by the path. We refer to such
a description as the _combinatorial representation_ of the path, and to the
total length of these sequences as the _complexity_ of $\pi$. In the remainder
of the paper, we will use $\pi(s,t)$ to denote an arbitrary minimum complexity
shortest path between $s$ and $t$. As we observed before (see Figure 2(b)), a
shortest path may still intersect a single portal edge many times, and hence
the complexity of a shortest path may be unbounded in terms of $n$ and $m$.

##### Isometry.

A map $f\colon X\to Y$ between metric spaces $X$ and $Y$ is an _isometry_ if
$d_{X}(x,x^{\prime})=d_{Y}(f(x),f(x^{\prime}))$ for all $x,x^{\prime}\in X$.
We say that $f$ is a _local isometry_ at a point $x$ if there exists an open
neighborhood $U_{x}$ of $x$ such that the restriction of $f$ to $U_{x}$ is an
isometry.

##### Equivalent portalgons.

Given a portalgon $\mathcal{P}$, there are many other portalgons that describe
the same surface $\Sigma$. For instance, we can always cut a fragment into two
smaller fragments by transforming a chord of the fragment into a portal, or,
assuming this does not cause any overlap, we can glue two fragments along a
portal, see Figure 5. More formally, two portalgons $\mathcal{P}$ and
$\mathcal{Q}$ are _equivalent_ , denoted $\mathcal{P}\equiv\mathcal{Q}$, if
there is a bijective isometry between them (i.e., if for any pair of points
$s,t\in\mathcal{P}$, their distance in $\mathcal{P}$ and $\mathcal{Q}$ is the
same).

Figure 5: Five equivalent portalgons, with the shortest path between (the
same) two points.

##### Happiness.

Our ultimate goal will be to find, for a given input portalgon, an equivalent
portalgon such that all its shortest paths have bounded complexity. To this
end, we introduce the notion of a happy portalgon, and more specifically, a
happy fragment of a portalgon.

Let $\mathcal{P}=(\mathcal{F},P)$ be a portalgon, let $F\in\mathcal{F}$ be a
fragment in $\mathcal{F}$, and let $\Pi(p,q)$ denote the set of all shortest
paths between $p,q\in\Sigma$. We define $c(X)$ as the number of connected
components in $X$. The _happiness_
$\mathcal{H}(F)=\max_{p,q\in\Sigma}\max_{\pi\in\Pi(p,q)}c(F\cap\pi)$ of
fragment $F$ is defined as the maximum number of times a shortest path $\pi$
between any pair of points $p,q\in\Sigma$ can go through the fragment. The
happiness of $\mathcal{P}$ is then defined as
$\mathcal{H}(\mathcal{P})=\max_{F\in\mathcal{F}}\mathcal{H}(F)$ the maximum
happiness over all fragments. We say that a portalgon is $h$-happy when
$\mathcal{H}(\mathcal{P})\leq h$. Further, we will sometimes refer to a
_happy_ portalgon, without an $h$ value, to mean $O(1)$-happy.

######  Lemma 2.1.

Let $\mathcal{P}=(\mathcal{F},P)$ be an $h$-happy portalgon, and let
$\mathcal{P}^{\prime}=(\mathcal{F}^{\prime},P^{\prime})$ be a triangulation of
$\mathcal{P}$. The happiness of $\mathcal{P}^{\prime}$ is at most $h$; that
is, $\mathcal{P}^{\prime}$ is an $h$-happy portalgon.

Note that if $\mathcal{P}$ has $n$ vertices and $m$ portals, any triangulation
$\mathcal{P}^{\prime}$ of $\mathcal{P}$ consists of $n$ vertices and $O(m+n)$
portals. The fact that in an $h$-happy portalgon a shortest path crosses every
portal at most $h-1$ times implies the following.

######  Lemma 2.2.

Let $\mathcal{P}$ be an $h$-happy portalgonand let $s$ and $t$ be two points
in $\mathcal{P}$. A shortest path $\pi(s,t)$ between $s$ and $t$ has
complexity $O(n+hm)$. This bound is tight in the worst case.

######  Proof 2.3.

The vertices of $\pi(s,t)$ are either: (i) $s$ or $t$ itself, (ii) vertices of
$\mathcal{P}$, or (iii) points in which $\pi(s,t)$ crosses a portal edge.
There are only two vertices of type (i) on $\pi(s,t)$. A shortest path can
visit any vertex of $\mathcal{P}$ at most once; hence, there are at most $n$
vertices of type (ii). Finally, since $\mathcal{P}$ is $h$-happy, $\pi(s,t)$
crosses every fragment $F\in\mathcal{F}$ at most $h$ times.

Figure 6: A simple $h$-happy portalgon in which a shortest path has complexity
$\Omega(hm)$ as it crosses $\Omega(m)$ portal edges (the blue portal edges)
$\Omega(h)$ times each.

A shortest path of complexity $\Omega(n)$ is easy to attain in a fragment
without portals and a chain with $\Omega(n)$ reflex vertices. We get the
$\Omega(hm)$ term using a portalgon like in Figure 6. For any $h$, we can
choose the length of the red portal so that the portalgon is $h$-happy.

##### Shortest path map.

Given a portalgon $\mathcal{P}$, a source point $s\in\Sigma$, and a region
$\mathcal{X}\subseteq\Sigma$ the shortest path map
$\operatorname{SPM}_{\mathcal{X}}(s)$ of $s$ is a subdivision of $\mathcal{X}$
into maximally connected regions, such that for all points $q$ in the interior
of a region $R\in\operatorname{SPM}_{\mathcal{X}}(s)$ the shortest path from
$s$ to $q$ is unique, and has the same combinatorial structure, i.e., visits
the same sequence of vertices and portal edges of $\mathcal{P}$. Note that the
complexity of $\operatorname{SPM}_{\mathcal{X}}(s)$ depends on the
representation of the surface $\Sigma=\Sigma(\mathcal{P})$, that is, the
portalgon $\mathcal{P}$. So changes to $\mathcal{P}$ may affect the complexity
of $\operatorname{SPM}_{\mathcal{X}}(s)$. For example, splitting faces of
$\mathcal{P}$ increases the complexity of
$\operatorname{SPM}_{\mathcal{X}}(s)$. Hence, when $\Sigma$ is fixed, an
important problem is to find a good portalgon (i.e. one for which
$\operatorname{SPM}(s)=\operatorname{SPM}_{\Sigma}(s)$ has low complexity)
representing it.

##### Intrinsic Delaunay triangulation.

A triangulation of a portalgon is an equivalent portalgon whose vertex set is
the same, and all of whose fragments are triangles. In particular, among all
such triangulations, the intrinsic Delaunay triangulation is such that for any
interior edge of the triangulation, for the two triangles $t$ and $t^{\prime}$
incident to that edge, the corners of $t$ and $t^{\prime}$ not incident to
that edge sum up to at most 180 degrees [4].

##  3 Shortest paths in portalgons

In this section we show how to compute the shortest path map
$\operatorname{SPM}_{\mathcal{P}}:=\operatorname{SPM}_{\mathcal{P}}(s)$ of a
source point $s$ in a $h$-happy triangulated portalgon $\mathcal{P}$. By Lemma
2.1 any $h$-happy portalgon can be transformed into a triangulated $h$-happy
portalgon by triangulating its fragments and replacing the resulting diagonals
by portals. For ease of description, we assume that any two triangles have at
most one edge in common, and that $s$ is a vertex of the triangulation. We can
again subdivide every triangle into $O(1)$ $h$-happy triangles to achieve
this.

For a path $\pi$ starting from the source $s$, define its signature, denoted
$\sigma(\pi)$, to be the sequence of vertices and portals it passes through.
Note that paths may simultaneously pass through a vertex and a portal (or
multiple portals incident to that vertex). In this case, we break ties in the
sequence by placing vertices before portals, and portals in the order that the
path would pass through them if it were perturbed away from vertices (in a
consistent way), where we always perturb the start of the path into a fixed
triangle $T_{s}$ incident to $s$.

If $\pi$ is a shortest path from the source $s$ to a point $p$ in a triangle
$T$, and $v$ is the last vertex on $\sigma(\pi)$, then the length of $\pi$ is
$d(s,v)+d(v,p)$, where $d(v,p)$ can be expressed as the length of a line
segment as follows. We think of $T$ as being embedded locally isometrically in
the Euclidean plane, and by unfolding the fragments that $\pi$ passes through
after $v$, we can compute a copy of $v$ in the plane, as well as copies of the
portals and triangles that $\pi$ passes through after $v$; see Figure 7. The
locations of these copies in the plane depend only on $\sigma(\pi)$ (but not
$p$ or $\pi$ itself). Then, $d(v,p)$ is the Euclidean distance between the
copies of $v$ and $p$ in the plane, and the segment connecting these copies
passes through all the unfolded copies of portals of $\sigma(\pi)$ after $v$.
Let $e$ be an edge of $T$, and define $I_{\sigma(\pi),e}$ to be the interval
of points $p$ on $e$ for which the segment $\overline{vp}$ passes through all
the unfolded copies of portals of $\sigma(\pi)$ after $v$. For a point $q$ in
$T$, define

$f_{\sigma(\pi)}(q)=\begin{cases}d(s,v)+\|\overline{vq}\|&\text{if the segment
$\overline{vq}$ passes through $I_{\sigma(\pi),e}$,}\\\
\infty&\text{otherwise.}\end{cases}$

Define $d_{\sigma(\pi)}(q)$ to be the infimum length over paths from $s$ to
$q$ with signature $\sigma(\pi)$. This infimum is not necessarily realized by
a path with the same signature, but is always realized by a path that
potentially bends around additional vertices after the last vertex of
$\sigma(\pi)$, which are therefore inserted in its signature. We say that such
a signature _reduces_ to $\sigma(\pi)$. Note that if $f_{\sigma(\pi)}(q)$ is
finite, then $f_{\sigma(\pi)}(q)=d_{\sigma(\pi)}(q)$. If $\pi$ is a shortest
path from $s$ to $p$, then $\pi$ has length $f_{\sigma(\pi)}(p)$. For a portal
$e$ of $T$, let $f_{\sigma(\pi)|e}\colon e\to\mathbb{R}\cup\\{\infty\\}$ be
the restriction of $f_{\sigma(\pi)}$ to points of $e$.

Figure 7: The length of the path $\pi$ from $s$ to point $p$ in triangle $T$
is $d(s,v)+\|p-v\|$. The signature of $\pi$ defines intervals
$I_{\sigma(\pi),e}$ and $I_{\sigma(\pi),e^{\prime}}$ on edges $e$ and
$e^{\prime}$ of $T$, as well as a distance function $d_{\sigma(\pi)}$
illustrated by the path to point $q$ in $T$.

###  3.1 A data structure for maintaining a lower envelope

Let $F$ be a set of $m$ partial continuous functions, each defined on a single
interval, and such that each pair of functions can intersect at most twice. We
describe a data structure storing the lower envelope $\mathrm{env}_{F}$ of
$F$, that supports the following operations:

NextLocalMinimum($\delta$):

report the smallest local minimum of $\mathrm{env}_{F}$ that is larger than
$\delta$.

NextVertex$(f,q)$:

given a function $f\in F$ that realizes $\mathrm{env}_{F}$ at point $q$, find
(if it exists) the lowest endpoint $(v,\delta^{\prime})$ of the segment of
$\mathrm{env}_{F}$ containing $(q,f(q))$ for which $\delta^{\prime}>f(q)$.

Insert($f$):

insert a new function into $F$.

We develop a simple static data structure supporting the NextLocalMinimum and
NextVertex operations, that we turn into an efficient insertion-only data
structure using the logarithmic method [3]. In our implementation of the
static structure, the two query operations may actually make modifications to
the static structure that will guarantee efficient amortized query times.

We represent $\mathrm{env}_{F}$ using $O(\log m)$ static data structures. Each
such static data structure stores the lower envelope $\mathrm{env}_{i}$ of a
subset $F_{i}$ of $2^{i}$ functions from $F$. In particular, it stores:

  1. (i)

a binary search tree of (a subset of) the intervals of $\mathrm{env}_{i}$,
ordered by $x$-coordinate of their left endpoint, and

  2. (ii)

a sorted list of local minima on $\mathrm{env}_{i}$ ordered on increasing
$y$-coordinate.

We can now easily answer NextLocalMinimum queries in $O(\log^{2}m)$ time: for
each of the $O(\log m)$ stored lower envelopes, we binary search in the list
of local minima to find the smallest minimum with value larger than $\delta$,
and report the smallest one overall.

Figure 8: In a NextVertex$(f,q)$ query we find $\mathrm{env}_{i}(q)$ on each
envelope $\mathrm{env}_{i}$ (shown in dark blue), and walk along
$\mathrm{env}_{i}$, to find the first intersection point $p$ of $f$ with
$\mathrm{env}_{i}$. The fat blue segments of $\mathrm{env}_{i}$ are, and will
forever be, dominated by $f$, hence we delete them.

To answer NextVertex$(f,q)$ queries we essentially compute the endpoints of
the segment of $\mathrm{env}_{F}$ containing $(q,\delta)$, and report the
lowest such endpoint with value larger than $\delta$. To find the right
endpoint of this segment, we do the following (finding the left endpoint is
symmetric). For each of the $O(\log m)$ static structures, we do a binary
search on the vertices of $\mathrm{env}_{i}$ to find the interval
$[v_{j-1},v_{j}]$ containing point $q$, and the function $f^{\prime}$ that
realizes $\mathrm{env}_{i}$ in this interval. We then find the first
intersection point $p$ of $f$ with $\mathrm{env}_{i}$ to the right of $q$ by
walking along $\mathrm{env}_{i}$ (see Figure 8). In particular, we compute the
intersection points of $f$ and $f^{\prime}$, and if there is such a point in
the interval $[q,v_{j}]$, we found point $p$. Otherwise, we continue the
search (walk) with the next interval $[v_{j},v_{j+1}]$. We can stop the walk
if we arrive at an interval whose left endpoint lies strictly below $f$ (in
that case there is no intersection on $\mathrm{env}_{i}$). All intervals
$[v_{j-1},v_{j}]$ that we encounter during this walk and in which $f$ lies
below $f^{\prime}$ in the entire interval will never show up on
$\mathrm{env}_{F}$ (since $f$ will never be deleted). Hence, we will delete
these intervals from $\mathrm{env}_{i}$. This allows us to bound the overall
time spent walking along $\mathrm{env}_{i}$ envelopes over all queries. The
running time of our query is thus $O(\sum_{i=0}^{O(\log
m)}|\mathrm{env}_{i}|+\ell)=O(\log
m\log|\mathrm{env}_{F}|+\ell)=O(\log^{2}m+\ell)$, where $\ell$ is the total
number of intervals deleted during this walk.

Finally, to handle an Insert$(f)$ operation; we create a new static data
structure lower envelope structure $\mathrm{env}_{0}$ representing just the
singleton set $F^{\prime}_{0}=\\{f\\}$. If there are ever two static data
structures representing sets $F_{i}$ and $F^{\prime}_{i}$ of the same size
$2^{i}$, we replace them by a data structure representing a new set
$F^{\prime}_{i+1}=F_{i}\cup F^{\prime}_{i}$ of size $2^{i+1}$. We can
construct this data structure by merging the two earlier structures: i.e., we
can simultaneously scan through $\mathrm{env}_{i}$ and
$\mathrm{env}^{\prime}_{i}$ creating the new combined envelope in time
$O(|\mathrm{env}_{i}|+|\mathrm{env}^{\prime}_{i}|+|\mathrm{env}^{\prime}_{i+1}|)=O(|\mathrm{env}^{\prime}_{i+1}|)$.
During this merge, we can mark the local minima that remain local minima. We
can then merge the sorted lists of marked local minima in linear time.

Next, we prove that the total number of intervals in the lower envelopes that
we create during a sequence of $m$ insertions is at most
$O(|\mathrm{env}_{F}|\log m)=O(\lambda_{4}(m)\log m)$, where $\lambda_{4}(n)$
is the maximum length of a Davenport-Schinzel sequence of order four on $n$
symbols. Hence, the amortized insertion time is $O((\lambda_{4}(m)/m)\log m)$.

######  Lemma 3.1.

The total number of intervals in the $\mathrm{env}_{i}$ envelopes created over
a sequence of $m$ insertions into $F$ is $O(\lambda_{4}(m)\log m)$.

######  Proof 3.2.

Consider the set of functions $F_{j}$ in the final structure, we bound all
intervals created due to functions in $F_{j}$ by $O(\lambda_{4}(2^{j})\log
m)$. It then follows that the total number of intervals created is bounded by
$\sum_{j=0}^{O(\log m)}O(\lambda_{4}(2^{j})\log m)=O(\lambda_{4}(2^{O(\log
m)})\log m)=O(\lambda_{4}(m)\log m)$ as claimed.

Clearly, there is at most one interval created due to $F_{0}$. For all
intervals created by functions in $F_{j}$, with $j>0$, their intervals were
created when we merged $\mathrm{env}_{i}$ and $\mathrm{env}^{\prime}_{i}$,
$0\leq i<j$, into an $\mathrm{env}_{i+1}$. Charge the cost of creating the
intervals from $\mathrm{env}_{i}$ and $\mathrm{env}^{\prime}_{i}$ to the
intervals of $\mathrm{env}_{i+1}$. It now follows that in the end, all costs
are charged to intervals of $\mathrm{env}_{j}$. Moreover, every interval in
$\mathrm{env}_{j}$ is charged at most $O(j)=O(\log m)$ times. Since
$\mathrm{env}_{j}$ consists of at most $O(\lambda_{4}(2^{j}))$ intervals the
lemma follows.

Since any interval can be deleted at most once, we thus obtain the following
result:

######  Lemma 3.3.

We can maintain the lower envelope $\mathrm{env}_{F}$ of a set $F$ of partial
functions $f$, each pair of which intersect each other at most twice, in a
data structure that: any sequence of $m$ Insert operations and $k$
NextLocalMinimum and NextVertex queries takes at most
$O(k\log^{2}m+\lambda_{4}(m)\log m)$ time.

###  3.2 SPM restricted to the edges

We first compute the shortest path map of $s$, restricted to the edges of the
portalgon. As in earlier work [22, 23] we propagate a wavefront of points at
distance $\delta$ from $s$ as we vary $\delta$ from $0$ to $\infty$. However,
it will be more convenient to view this as a collection of simultaneous
sweepline algorithms. For each portal edge $e$, we sweep a horizontal line at
height $\delta$ upward through the “position along $e$ $\times$ distance from
$s$” space (see Figure 9), while we construct the part of
$\operatorname{SPM}_{e}$ below the sweep line. The main challenge is computing
the next event –the first vertex in the lower envelope of the distance
functions above the sweep line– in time.

For each portal $e$ connecting two fragments $T_{A}$ and $T_{B}$, we maintain
the following information:

Figure 9: The information that we maintain while computing the SPM of the
edges.

  1. 1.

Let $S_{A}(e,\delta)$ (resp. $S_{B}(e,\delta)$) be the set of signatures of
shortest paths222For efficiency, we symbolically ensure uniqueness of shortest
paths by breaking ties consistently based on their signatures.  from $s$ to
points on the boundary of $T_{A}$ (resp. $T_{B}$), where the last element of
the signature is not $e$, and the length of the path is at most $\delta$. We
represent each signature $\sigma\in S_{A}(e,\delta)\cup S_{B}(e,\delta)$
implicitly by storing the interval $I_{\sigma,e}$, the position of (the
unfolded copy of) the last vertex $v$ on $\sigma$, and $d(s,v)$, so that we
can compute $f_{\sigma|e}$ in constant time. For the purpose of recovering the
shortest path map, we additionally store a pointer to the corresponding data
on the previous edge on $\sigma$ (if any).

  2. 2.

We store the lower envelope $\mathrm{env}_{A}(e,\delta)$ of the functions
$f_{\sigma|e}$, where $\sigma$ ranges over the signatures $S_{A}(e,\delta)$,
in the data structure of Lemma 3.3. Based on $S_{B}$, we symmetrically define
and store $\mathrm{env}_{B}(e,\delta)$.

  3. 3.

Let $\mathrm{env}(e,\delta)$ be the lower envelope of the functions
$\mathrm{env}_{A}(e,\delta)$ and $\mathrm{env}_{B}(e,\delta)$. We maintain
only the part of $\mathrm{env}(e,\delta)$ that lies below the sweep line,
denoted $\mathrm{env}^{\leq\delta}(e,\delta)$.

Intuitively, $\mathrm{env}^{\leq\delta}(e,\delta)$ will be the part of
$\operatorname{SPM}_{e}$ within distance $\delta$ from $s$. We store it in a
balanced binary search tree of breakpoints along the edge. Note that some of
these break points may lie on the sweep line, and thus move continuously with
the sweep line.

  4. 4.

We maintain a binary search tree $\mathrm{env}^{=\delta}(e,\delta)$ storing
the intersection points of $\mathrm{env}_{A}(e,\delta)$ and
$\mathrm{env}_{B}(e,\delta)$ with the sweep line, in order along the sweep
line. For each such intersection point we store the function(s) from
$\mathrm{env}_{A}(e,\delta)$ or $\mathrm{env}_{B}(e,\delta)$ realizing this
intersection point.

  5. 5.

Finally, we maintain a set of events pertaining to the edge $e$. We aggregate
the events of all edges in a global priority queue, and use it to advance the
sweep line algorithm to the next relevant value. The events that we store for
an edge $e$ are the values $\delta^{\prime}>\delta$ such that

    1. (a)

$\delta^{\prime}$ corresponds to a minimum of a function $f_{\sigma|e}$ with
$\sigma\in S_{A}(e,\delta)\cup S_{B}(e,\delta)$,

    2. (b)

$\delta^{\prime}$ corresponds to a vertex of $\mathrm{env}_{A}(e,\delta)$ or
$\mathrm{env}_{B}(e,\delta)$, in particular an endpoint of one of the edges
that currently appear in $\mathrm{env}^{=\delta}(e,\delta)$, or

    3. (c)

$\delta^{\prime}$ corresponds to an intersection between functions
$f_{\sigma|e}$ on $\mathrm{env}_{A}(e,\delta)$ and $f_{\sigma^{\prime}|e}$ on
$\mathrm{env}_{B}(e,\delta)$, where $f_{\sigma|e}$ and $f_{\sigma^{\prime}|e}$
are neighbors in $\mathrm{env}^{=\delta}(e,\delta)$.

For each event, we also keep track of the type and corresponding functions.

Note that $\mathrm{env}^{\leq\infty}(e,\infty)=\mathrm{env}(e,\infty)$. Before
we show how to maintain all the above information, we show that this
information indeed corresponds to the shortest path map.

######  Lemma 3.4.

$\mathrm{env}^{\leq\delta}(e,\delta)$ encodes the shortest paths of length
$\leq\delta$ to points on the edge $e$.

######  Proof 3.5.

For any point $q\in e$ the (due to tie-breaking, unique) shortest path $\pi$
from $s$ to $q$ arrives from either $T_{A}$ or $T_{B}$. If $\pi$ has length at
most $\delta$, then $\sigma(\pi)$ appears in either $S_{A}(e,\delta)$ or
$S_{B}(e,\delta)$, and hence $f_{\sigma(\pi)|e}(q)$ lies on or above the lower
envelope $\mathrm{env}^{\leq\delta}(e,\delta)$. Conversely, any point on
$\mathrm{env}^{\leq\delta}(e,\delta)$ with finite function value corresponds
to a path of that length, so $f_{\sigma(\pi)|e}(q)$ indeed lies on
$\mathrm{env}^{\leq\delta}(e,\delta)$.

For $\delta=0$ and any edge $e$, we initialize $S_{A}(e,0)$ to be empty if
$T_{A}$ does not contain $s$, and to consist of a single sequence consisting
of $s$ and the edges around $s$ between $T_{s}$ and $T_{A}$ (excluding $e$)
otherwise. We initialize $S_{B}$ symmetrically. Based on this,
$\mathrm{env}_{A}$ and $\mathrm{env}_{B}$ are initially lower envelopes each
of at most one function, where $\mathrm{env}^{\leq\delta}(e,\delta)$ is empty
unless $s\in e$. The priority queue of events related to $e$ therefore
consists of at most one event: $\mathrm{next}(e,0)$ is the distance from $s$
to $e$ inside $T_{A}$ or $T_{B}$ (if $s$ lies in $T_{A}$ or $T_{B}$), and
$\infty$ otherwise. It remains to argue that we can correctly maintain the
information as $\delta$ increases.

Figure 10: (a) The different event types: a. local minima in
$\mathrm{env}_{A}$ or $\mathrm{env}_{B}$, b. breakpoints of $\mathrm{env}_{A}$
or $\mathrm{env}_{B}$, and two events of type c. first intersections of
$\mathrm{env}_{A}$ and $\mathrm{env}_{B}$. (b) We will detect the intersection
between $\mathrm{env}_{A}$ and $\mathrm{env}_{B}$ once $f_{\sigma|e}$ and
$f_{\sigma^{\prime}|e}$ become neighbors in $\mathrm{env}^{=\delta}$ at time
$\delta^{+}$.

Observe, that our events allow us to correctly detect the first time
$\delta^{\prime}>\delta$ at which
$\mathrm{env}^{\leq\delta^{\prime}}(e,\delta)$ differs combinatorially from
$\mathrm{env}^{\leq\delta}(e,\delta)$, provided that $S_{A}(e,\delta)$ and
$S_{B}(e,\delta)$ remain unchanged. In particular, any local minimum
$\mathrm{env}(e,\delta)$ is a local minimum of $\mathrm{env}_{A}(e,\delta)$ or
$\mathrm{env}_{B}(e,\delta)$, and any vertex of $\mathrm{env}(e,\delta)$ is
either a vertex of $\mathrm{env}_{A}(e,\delta)$ or
$\mathrm{env}_{B}(e,\delta)$, or an intersection point of
$\mathrm{env}_{A}(e,\delta)$ with $\mathrm{env}_{B}(e,\delta)$. The functions
$\mathrm{env}_{A}(e,\delta)$ or $\mathrm{env}_{B}(e,\delta)$ can only
intersect at time $\delta^{\prime}$ when $f_{\sigma|e}(e,\delta)$ and
$f_{\sigma^{\prime}|e}(e,\delta)$ are neighbors on the sweep line at some time
$\delta<\delta^{\prime}$.

##### Event handling.

At an event (of any type), the order in which the functions of
$\mathrm{env}_{A}(e,\delta)$ and $\mathrm{env}_{B}(e,\delta)$ intersect the
sweep line changes. We therefore update $\mathrm{env}^{=\delta}(e,\delta)$ by
removing and inserting the appropriate functions associated with this event,
and additionally make sure that we discover any additional events.

For each newly inserted function $f_{\sigma|e}\in\mathrm{env}_{A}(e,\delta)$
that intersects the sweep line in a point $(q,\delta)$, we use a
NextVertex$(f_{\sigma|e},q)$ query to find the next type b. event where the
sweep line will pass over a vertex of $\mathrm{env}_{A}(e,\delta)$. We use an
analogous query for any function
$f_{\sigma^{\prime}|e}\in\mathrm{env}_{B}(e,\delta)$.

Furthermore, for any function $f_{\sigma|e}\in\mathrm{env}_{A}(e,\delta)$ that
has a new neighbor $f_{\sigma^{\prime}|e}\in\mathrm{env}_{B}(e,\delta)$ in the
order along the sweep line, we compute if these functions intersect above the
sweep line, and if so create a new type c. event in the event queue. We handle
the case where $f_{\sigma|e}\in\mathrm{env}_{B}(e,\delta)$ analogously.
Furthermore, we remove any type c. events of functions that are no longer
neighbors.

If this event was a local minimum of $\mathrm{env}_{A}(e,\delta)$ we extract
the next local minimum of $\mathrm{env}_{A}(e,\delta)$ above the sweep line
using a call to NextLocalMinimum on $\mathrm{env}_{A}(e,\delta)$. We handle
local minima of $\mathrm{env}_{B}(e,\delta)$ analogously.

Finally, as a result of the event, a new function, say $f_{\sigma^{\prime}|e}$
from $\mathrm{env}_{B}(e,\delta)$, may have appeared on
$\mathrm{env}^{\leq\delta}(e,\delta)$. Hence, we insert it into
$\mathrm{env}^{\leq\delta}(e,\delta)$, and propagate $\sigma^{\prime}$,
extended by edge $e$, into the sets $S_{B}(e^{\prime},\delta)$ of the other
two edges $e^{\prime}$ incident to $T_{A}$. We therefore use an Insert call to
insert a new function into $\mathrm{env}_{A}(e^{\prime},\delta)$ (if it is not
already present), and NextLocalMinimum$(\delta)$ call on
$\mathrm{env}_{A}(e^{\prime},\delta)$ to make sure we update the next local
minimum.

When we insert $f_{\sigma^{\prime}|e^{\prime}}$ into
$\mathrm{env}_{A}(e^{\prime},\delta)$ it may already intersect the sweepline
in the $e^{\prime}\times\mathit{distance}$ space; i.e. there may be an
interval of points $q^{\prime}\in[a^{\prime},b^{\prime}]$ on $e^{\prime}$ for
which $f_{\sigma^{\prime}|e^{\prime}}(q^{\prime})\leq\delta$. We therefore
insert the at most two intersection points of $f_{\sigma^{\prime}|e^{\prime}}$
with the sweep-line ($a^{\prime}$ and $b^{\prime}$) into
$\mathrm{env}_{=}(e^{\prime},\delta)$, and in turn update the at most eight
type b. and c. events (four each) caused by these new intersection points.

Note however, that our invariants guarantee that any point $q^{\prime}$ in the
interval $[a^{\prime},b^{\prime}]$ on which
$f_{\sigma^{\prime}|e^{\prime}}(q^{\prime})\leq\delta$ we actually have that
$\mathrm{env}^{\leq\delta}(e^{\prime},\delta)(q^{\prime})\leq
f_{\sigma^{\prime}|e^{\prime}}(q^{\prime})$, hence
$\mathrm{env}^{\leq\delta}(e^{\prime},\delta)$ remains unchanged (and hence no
further updates are triggered).

######  Lemma 3.6.

For any point $q^{\prime}\in[a^{\prime},b^{\prime}]\subseteq e^{\prime}$ we
have that $\mathrm{env}^{\leq\delta}(e^{\prime},\delta)(q^{\prime})\leq
f_{\sigma^{\prime}|e^{\prime}}(q^{\prime})$.

######  Proof 3.7.

Assume by contradiction that there is a point
$q^{\prime}\in[a^{\prime},b^{\prime}]$ for which
$f_{\sigma^{\prime}|e^{\prime}}(q^{\prime})<\mathrm{env}^{\leq\delta}(e^{\prime},\delta)(q^{\prime})$.
Moreover, let $q^{\prime}$ be the closest such point over all edges in the
portalgon; i.e. so that
$f_{\sigma^{\prime}|e^{\prime}}(q^{\prime})=d(s,q^{\prime})=\delta_{1}\leq\delta$
(and thus for any $\delta_{0}<\delta_{1}$ the function
$\mathrm{env}^{\leq\delta}(e,\delta_{0})$ correctly represents the shortest
path map on (any) edge $e$). Let $q$ be the point where the shortest path
$\pi(\sigma^{\prime})$ to $q^{\prime}$ intersects $e$; this subpath $\pi_{0}$
thus has length $f_{\sigma^{\prime}|e}(q)=\delta_{0}<\delta_{1}$. By subpath
optimality, $\pi_{0}$ is a shortest path, and thus $\delta_{0}=d(s,q)$. We
then have that
$\mathrm{env}^{\leq\delta}(e,\delta_{0})=f_{\sigma^{\prime}|e}(q)$. However,
it then follows that $\sigma^{\prime}$ was already inserted into
$S_{A}(e^{\prime},\delta_{0})\subseteq S_{A}(e^{\prime},\delta)$ at “time”
$\delta_{0}$. Therefore,
$\mathrm{env}^{\leq\delta}(e^{\prime},\delta)(q^{\prime})\leq\mathrm{env}_{A}(e^{\prime},\delta)(q^{\prime})\leq
f_{\sigma^{\prime}|e^{\prime}}(q^{\prime})$, and thus we obtain a
contradiction.

######  Remark 3.8.

Mitchell, Mount, and Papadimitriou [22] use a similar overall algorithm. They
define a notion of _$T_{A}$ -free_ paths that arrive at edge $e$ from $T_{B}$.
They prove that these paths act sufficiently like “real” shortest paths so
that they can explicitly maintain the set of shortest $T_{A}$-free and
$T_{B}$-free paths. Unfortunately, some of the arguments used hold only when a
shortest path may cross a portal edge at most once (that is, when the
portalgon is $1$-happy). In case of the weighted region problem, Mitchel and
Papadimitriou show how to deal with this by extending this notion of _$T_{A}$
-free_ paths to _locally_ _$T_{A}$ -free_ paths [23]. However, it is unclear
how to bound the number of such paths when the genus may be non-zero.

In contrast, we insert a signature $\sigma$ into $S_{B}(e,\delta)$ _only_ when
we can guarantee that $\sigma$ produces a shortest path to a point on edge of
$T_{B}$ (rather than already when it produces a locally shortest $T_{B}$-free
path to such an edge). We can thereby limit the size of the sets
$S_{B}(e,\delta)$, by charging them to intervals in the actual shortest path
map.

##### Analysis.

Let $k=|\operatorname{SPM}_{\partial\mathcal{P}}|$ denote the complexity of
the shortest path restricted to the edges. We first show that the total number
of events, over all edges of $\mathcal{P}$ is $O(\lambda_{4}(k))$. We first
count the number of events for a fixed edge $e$.

Observe that for any $\delta$, $S_{A}(e,\delta)\subseteq S_{A}(e,\infty)$,
hence every event of type a. is a minimum of a function $f_{\sigma|e}$ with
$\sigma\in S_{A}(e,\infty)\cup S_{B}(e,\infty)$. As each function is unimodal
it contributes at most one minimum, and hence the total number of events of
type a. is $O(k_{A}+k_{B})$, where $k_{A}=|S_{A}(e,\infty)|$ and
$k_{B}=|S_{B}(e,\infty)|$.

######  Lemma 3.9.

The total number of events of type b. corresponding to vertices in
$\mathrm{env}_{A}(e,\delta)$, over all values $\delta$, is
$O(\lambda_{4}(k_{A}))$.

######  Proof 3.10.

For each signature $\sigma\in S_{A}(e,\infty)$, consider the time $\delta$ at
which $\sigma$ was added to $S_{A}(e,\delta)$. Now restrict each function
$f_{\sigma|e}(q)$ to the domain on which $f_{\sigma|e}(q)\geq\delta$. This
essentially splits $f_{\sigma|e}$ into two functions. Let $F^{\prime}$ denote
the resulting set of $O(k_{A})$ functions, and let $\mathrm{env}_{F^{\prime}}$
be its lower envelope. It follows that this lower envelope has complexity
$O(\lambda_{4}(k_{a}))$ [25].

At every event b. corresponding to $\mathrm{env}_{A}(e,\delta)$, for some
value $\delta$, the sweepline passes through a vertex $v=(q,\delta)$ of
$\mathrm{env}_{A}(e,\delta)$. We claim that $v$ is also a vertex
$\mathrm{env}_{F^{\prime}}$. As the sweepline passes through such a vertex at
most once, the number of such events is thus at most $O(\lambda_{4}(k_{a}))$.

Since $v$ is a vertex of $\mathrm{env}_{A}(e,\delta)$, it is an endpoint of
(the graph of) a function in $F^{\prime}$. Next, we argue that
$\mathrm{env}_{A}(e,\delta)(q)\leq\mathrm{env}_{F^{\prime}}(q)$, and thus $v$
must also lie on $\mathrm{env}_{F^{\prime}}$.

For any time $\delta$, and any point $q$ we have
$\mathrm{env}_{A}(e,\delta)\leq\mathrm{env}_{F^{\prime}}(q)$: Assume by
contradiction that
$f^{\prime}_{\sigma|e}(q)=\mathrm{env}_{F^{\prime}}(q)=\delta_{2}<\mathrm{env}_{A}(e,\delta)$.
So $\sigma$ was added to $S_{A}(e,\infty)$ at some time
$\delta_{1}\leq\delta_{2}$. However, then $\sigma\in S(e,\delta)$, and thus
$\mathrm{env}_{A}(e,\delta)\leq f_{\sigma|e}(q)=\delta_{2}$. Contradiction. We
thus have $\mathrm{env}_{A}(e,\delta)\leq\mathrm{env}_{F^{\prime}}(q)$, which
completes the proof.

By Lemma 3.9 (and a symmetric counterpart for $\mathrm{env}_{B}$), the number
of events of type b. is at most $O(\lambda_{4}(k_{A})+\lambda_{4}(k_{B}))$.
Every event of type c. produces a vertex of
$\mathrm{env}^{\leq\delta}(e,\delta)$, and thus of $\operatorname{SPM}_{e}$.
Hence, it follows that the total number of events on $e$ is
$O(\lambda_{4}(k_{A})+\lambda_{4}(k_{B}))+|\operatorname{SPM}_{e}|)$.

A signature $\sigma$ appears in $S_{B}(e,\delta)$ only when there is a
shortest path to another edge $e^{\prime}$ of $T_{B}$. Since every such edge
$e^{\prime}$ propagates to at most four edges (of the two triangles incident
to $e^{\prime}$) it then follows that
$\sum_{e\in\partial\mathcal{P}}(|S_{A}(e,\delta)|+|S_{B}(e,\delta)|)=O(|\operatorname{SPM}_{\partial\mathcal{P}}|)$.
Therefore, the total number of events, over all edges $e$, is
$O(\lambda_{4}(k))$ as claimed.

For every edge $e$, and at any time $\delta$, the size of
$\mathrm{env}^{=\delta}(e,\delta)$ is at most
$O(|\mathrm{env}_{A}(e,\delta)|+|\mathrm{env}_{B}(e,\delta)|)$, as every
function intersects the sweep line at most twice. Furthermore, as we argued
above, the size of all those functions $\mathrm{env}_{A}(e,\delta)$,
$\mathrm{env}_{B}(e,\delta)$, $\mathrm{env}^{\leq\delta}(e,\delta)$, over all
edges $e$, is at most $O(\lambda_{4}(k))$.

To handle an event on edge $e$, we use a constant number of update operations
on the event queue(s), $\mathrm{env}^{\leq\delta}(e,\delta)$, and
$\mathrm{env}^{=\delta}(e,\delta)$, and a constant number of calls to Insert,
NextLocalMinimum, and NextEvent on $\mathrm{env}_{A}(e,\delta)$ and
$\mathrm{env}_{B}(e,\delta)$. It follows the former operations take only
$O(\log k)$ time, and by Lemma 3.3, the total cost of the operations on
$\mathrm{env}_{A}(e,\delta)$ and $\mathrm{env}_{B}(e,\delta)$, over all edges,
is $O(\lambda_{4}(k)\log^{2}k)$. It follows that we can thus compute
$\operatorname{SPM}_{\partial\mathcal{P}}$ in $O(\lambda_{4}(k)\log^{2}k)$
time.

##### Bounding the complexity of $\operatorname{SPM}_{\partial\mathcal{P}}$.

We now prove that $|\operatorname{SPM}_{\partial\mathcal{P}}|=k=O(n^{2}h)$.

######  Lemma 3.11.

For any three points $p_{1},q,p_{2}$ in order on an edge $e$ and any signature
$\sigma$ in $S_{A}(e,\delta)$, if $d_{\sigma|e}$ lies on
$\mathrm{env}^{\leq\delta}(e,\delta)$ at both $p_{1}$ and $p_{2}$, but not at
$q$, then there does not exist any signature $\tau\in S_{A}(e,\delta)$ such
that $d_{\tau|e}$ lies on $\mathrm{env}^{\leq\delta}(e,\delta)$ at $q$.
Symmetric properties apply to $\sigma\in S_{B}(e,\delta)$.

######  Proof 3.12.

We prove this by induction on the length of the signature $\sigma$. If
$\sigma$ consists of just $s$, and $e$ is an edge incident to $s$, then
$d_{\sigma|e}$ is simply the distance along $e$ from $s$. Assume without loss
of generality that $q$ lies on the segment $\overline{sp_{1}}$ of $e$
(otherwise swap $p_{1}$ and $p_{2}$). If a signature $\tau$ as described would
exist, then $d_{\tau|e}(p_{2})\leq
d_{\tau|e}(q)+\overline{qp_{2}}<d_{\sigma|e}(q)+\overline{qp_{2}}=d_{\sigma|e}(p_{2})$,
which would contradict that $d_{\sigma|e}$ lies on
$\mathrm{env}^{\leq\delta}(e,\delta)$ at $p_{2}$.

The case where $\sigma$ consists of just $s$, but $e$ is the edge of $T_{s}$
not incident to $s$ is an easier version333Because it forces
$p^{\prime}_{1}=q^{\prime}=p^{\prime}_{2}=s$. of the case where $\sigma$ is
not just $s$, which we hence omit.

Now consider the case where $\sigma$ consists of not just $s$. Let $\pi_{1}$
and $\pi_{2}$ be shortest paths from $s$ to $p_{1}$ and $p_{2}$ whose
signatures reduce to $\sigma$. Then $\pi_{1}$ has length $d_{\sigma|e}(p_{1})$
and $\pi_{2}$ has length $d_{\sigma|e}(p_{2})$. Let $e^{\prime}$ be the last
edge that these paths visit (before $e$), and let $p^{\prime}_{1}$ and
$p^{\prime}_{2}$ respectively be their last point of intersection with
$e^{\prime}$. Now, assume for a contradiction that a signature $\tau$ as
described does exist. Let $\rho$ be the corresponding path from $s$ to $q$ of
length $d_{\tau|e}(q)$ whose signature reduces to $\tau$. By Lemma 3.4,
$\pi_{1}$, $\pi_{2}$, and $\rho$ are shortest paths.

See Figure 11 (a). If $\rho$ crosses $\overline{p^{\prime}_{1}p_{1}}$ or
$\overline{p^{\prime}_{2}p_{2}}$ in a point $x$, then we can replace the part
of $\pi_{1}$ or $\pi_{2}$ after $x$ to obtain a path from $s$ to $q$ of length
at most $\|\rho\|$ whose signature reduces to $\sigma$, contradicting that
$d_{\sigma|e}(q)>d_{\tau|e}(q)$. Because $\rho$ does not cross
$\overline{p^{\prime}_{1}p_{1}}$ or $\overline{p^{\prime}_{2}p_{2}}$, $\rho$
must enter $T_{A}$ in a point $q^{\prime}$ on $e^{\prime}$ that lies between
$p^{\prime}_{1}$ and $p^{\prime}_{2}$, see Figure 11 (b). Let $T_{C}$ be the
second triangle incident to $e^{\prime}$. Let $\sigma^{\prime}$ and
$\tau^{\prime}$ be signatures in $S_{C}(e^{\prime},\delta)$ such that
$d_{\sigma^{\prime}|e^{\prime}}(p^{\prime}_{1})$,
$d_{\sigma^{\prime}|e^{\prime}}(p^{\prime}_{2})$, and
$d_{\tau^{\prime}|e^{\prime}}(q^{\prime})$ lie on
$\mathrm{env}(e^{\prime},\delta)$ (such signatures exist because the subpaths
of $\pi_{1}$, $\pi_{2}$, and $\rho$ until $p^{\prime}_{1}$, $p^{\prime}_{2}$,
and $q^{\prime}$ are shortest paths of length at most $\delta$). Because
$d_{\tau|e}(q)<d_{\sigma|e}(q)$, we have
$d_{\tau^{\prime}|e^{\prime}}(q^{\prime})<d_{\sigma^{\prime}|e^{\prime}}(q^{\prime})$,
and hence $d_{\sigma^{\prime}|e^{\prime}}$ does not lie on
$\mathrm{env}^{\leq\delta}(e^{\prime},\delta)$ at $q^{\prime}$. By induction,
there does not exist any signature $\tau^{\prime\prime}\in
S_{C}(e^{\prime},\delta)$ such that $d_{\tau^{\prime\prime}|e^{\prime}}$ lies
on $\mathrm{env}^{\leq\delta}(e^{\prime},\delta)$ at $q^{\prime}$, but
$\tau^{\prime}$ is such a signature, which is a contradiction.

Figure 11: Cases of Lemma 3.11. Only the last segments of $\pi_{1}$, $\rho$,
and $\pi_{2}$ are depicted.

######  Lemma 3.13.

The complexity of $\mathrm{env}^{\leq\delta}(e,\delta)$ is
$O(|S_{A}(e,\delta)\cup S_{B}(e,\delta)|)$.

######  Proof 3.14.

Let $\Gamma$ be the sequence of signatures $\sigma$ in $S_{A}(e,\delta)\cup
S_{B}(e,\delta)$ whose distance functions $f_{\sigma|e}$ appear on
$\mathrm{env}^{\leq\delta}(e,\delta)$ as we traverse $e$ from left to right.
We argue that any contiguous subsequence $\Gamma^{\prime}$ of $\Gamma$ of
length $c+2$ contains a signature that did not appear on $\Gamma$ before,
where $c=O(1)$ is the number of times any pair of functions $f_{\sigma|e}$ and
$f_{\sigma^{\prime}|e}$ can intersect. Note that if a contiguous subsequence
contains at least two signatures from $S_{A}(e,\delta)$ (or from
$S_{B}(e,\delta)$), then by Lemma 3.11, the latter cannot have appeared on
$\Gamma$ before. On the other hand, if $\Gamma^{\prime}$ contains at most one
signature from each $S_{A}(e,\delta)$ and $S_{B}(e,\delta)$, then the length
of $\Gamma^{\prime}$ is at most the complexity of the lower envelope of some
$f_{\sigma|e}$ and $f_{\sigma^{\prime}|e}$, which is at most $c+1=O(1)$. It
follows that the length of $\Gamma$, and hence the complexity of
$\mathrm{env}^{\leq\delta}(e,\delta)$ is $O(|S_{A}(e,\delta)\cup
S_{B}(e,\delta)|)$.

######  Lemma 3.15.

For an $h$-happy portalgon, the complexity of the shortest path map restricted
to the edges is $O(n^{2}h)$.

######  Proof 3.16.

The complexity of the shortest path map (restricted to edges) corresponds to
the total complexity of $\mathrm{env}(e,\infty)$ (summed over all edges $e$),
which by Lemma 3.13 is linear in the number of signatures appearing in
$S_{A}(e,\infty)\cup S_{B}(e,\infty)$. For a signature $\sigma$ corresponding
to a point on an edge $e$, the last element of $\sigma$ is $e$, so points on
distinct edges have distinct signatures. Hence, the complexity of the shortest
path map is bounded by the total number of signatures.

We bound the total number of signatures of shortest paths by considering the
prefix tree of these signatures. Any edge appears at most $h$ times on the
signature of any shortest path, so the length of any such signature is
$O(nh)$. Hence, the depth of the prefix tree is $O(nh)$.

Observe that any node in the prefix tree has $O(1)$ children: a prefix
corresponds to a unique triangle, and can be extended only by appending one of
the constantly many vertices or edges incident to that triangle.

We show that only $O(n)$ nodes have multiple children. Due to tie-breaking,
any vertex $v$ corresponds to a unique shortest path, so the prefix tree
contains a unique signature that ends in $v$. We also show that for any
triangle $T_{A}$ with edges $e$, $e_{1}$, and $e_{2}$, there is at most one
prefix $\sigma$ ending in $e$ such that both $\sigma e_{1}$ and $\sigma e_{2}$
are prefixes of shortest paths. Let $p_{1}$ and $p_{2}$ be points on $e$
corresponding to shortest paths with signatures $\sigma e_{1}$ and $\sigma
e_{2}$. By Lemma 3.11 the shortest paths entering $T_{A}$ between $p_{1}$ and
$p_{2}$ (and thus all appear in $S_{B}(e,\infty)$, where $T_{B}\neq T_{A}$ is
the other triangle incident to $e$) all have signature $\sigma$.

Now suppose for a contradiction that there is a second signature
$\sigma^{\prime}$ such that both $\sigma^{\prime}e_{1}$ and
$\sigma^{\prime}e_{2}$ are prefixes of shortest paths, then similarly, these
paths enter $T_{A}$ through points $p^{\prime}_{1}$ and $p^{\prime}_{2}$,
between which the signature is $\sigma^{\prime}$. Therefore, the segments
$\overline{p_{1}p_{2}}$ and $\overline{p^{\prime}_{1}p^{\prime}_{2}}$ are
interior-disjoint, but this means that either the shortest paths with
signatures $\sigma e_{1}$ and $\sigma^{\prime}e_{2}$, or the shortest paths
with signatures $\sigma e_{2}$ and $\sigma^{\prime}e_{1}$ must cross, which is
impossible.

It follows that only $O(n)$ nodes of the prefix tree have multiple children.
Because all nodes have constant degree, the prefix tree has only $O(n)$
leaves. Combining this with the $O(nh)$ depth, there are $O(n^{2}h)$
signatures in total over all shortest paths.

We thus obtain the following result.

######  Lemma 3.17.

Let $\mathcal{P}$ be a triangulated $h$-happy portalgon with $n$ vertices and
$m$ portals, and let $s$ be a given source point. The shortest path map
$\operatorname{SPM}_{\partial\mathcal{P}}(s)$ of $s$ has complexity
$k=O(n^{2}h)$ and can be computed in $O(\lambda_{4}(k)\log^{2}k)$ time.

###  3.3 Extension to the interior

We now extend the shortest path map $\operatorname{SPM}_{\partial T}$ on the
boundary of a triangle $T$ into the shortest path map of the entire triangle
$T$. When $\operatorname{SPM}_{\partial T}$ consists of $m$ intervals,
$\operatorname{SPM}_{T}$ has complexity $O(m)$ and can be computed in $O(m\log
m)$ time, for example using the Build-Subdivision algorithm of Mitchell et al.
[22, Lemma 8.2]. Applying this to all triangles in the portalgon, we obtain
the following result.

######  Theorem 3.18.

Let $\mathcal{P}$ be a triangulated $h$-happy portalgon with $n$ vertices and
$m$ portals, and let $s$ be a given source point. The shortest path map
$\operatorname{SPM}_{\mathcal{P}}(s)$ of $s$ has complexity $k=O(n^{2}h)$ and
can be computed in $O(\lambda_{4}(k)\log^{2}k)$ time.

##  4 Existence of happy portalgons

In this section, we show that for every portalgon there exists an equivalent
$O(1)$-happy portalgon; specifically, the intrinsic Delaunay triangulation [4]
$\mathcal{T}$ of $\Sigma$ induces a happy portalgon, whose fragments
correspond to the triangles of $\mathcal{T}$. The resulting portalgon may have
more fragments than the original, but its total complexity is still linear.
While our proof is constructive, its running time may be unbounded.

###  4.1 Intrinsic Delaunay triangulation

Let $\mathcal{T}$ be a triangulated portalgon444We assume a triangulated
portalgon for ease of argumentation in this section; note that any portalgon
can easily be transformed into a triangulated portalgon by triangulating its
fragments and replacing the resulting diagonals by portals. and let $\Sigma$
be its surface; let $V$ be the set of vertices of $\Sigma$. Intuitively, the
intrinsic Delaunay triangulation of $\Sigma$ has a (straight) edge between two
vertices $u,v\in V$ when there exists a circle with $u$ and $v$ on its
boundary, and which contains no other vertices of $V$ when we “unfold”
$\Sigma$, for example by identifying edges of $\mathcal{T}$ as in Section 3.

To simplify geometric arguments, we derive a simply-connected space
$\hat{\Sigma}$ from $\Sigma$. We can think of $\hat{\Sigma}$ as the universal
cover of $\Sigma\setminus V$, with vertices reinserted at the corresponding
locations. More formally, we can define $\hat{\Sigma}$ by considering the
directed fragment graph $G$ of $\mathcal{T}$. For any portal $e$ of
$\mathcal{T}$, we denote by $T_{{e^{-}}},T_{{e^{+}}}\in\mathcal{F}$ the
triangles (nodes of $G$) that contain the respective portal edge; $G$ has a
link $\dot{e}$ from $T_{{e^{-}}}$ to $T_{{e^{+}}}$ and a link $\dot{e}^{-1}$
from $T_{{e^{+}}}$ to $T_{{e^{-}}}$. We say that $\dot{e}$ and $\dot{e}^{-1}$
are inverses of each other. A walk in $G$ from a triangle $T$ to a triangle
$T^{\prime}$ is a (possibly empty if $T=T^{\prime}$) sequence of links of $G$,
such that $T$ is the source of the first link, and the source of the
$(i+1)$-st is the target of the $i$-th link, and the target of the last link
is $T^{\prime}$. For a walk $w$ from $T$ to $T^{\prime}$, we write $w\colon
T\to_{G}T^{\prime}$ and say that a walk is _backtracking_ if it contains two
consecutive links that are inverses of each other. Fix an arbitrary root
triangle $T_{0}$, and for a walk $w\colon T_{0}\to_{G}T$, let $T_{w}$ be a
copy of the target triangle $T$ placed in the Euclidean plane by unfolding
$T_{0},T_{1},\ldots,T_{w}$ along their common portals. Let
$\hat{\mathcal{F}}=\bigsqcup\\{T_{w}\mid T\in\mathcal{F},w\colon T_{0}\to
T,\text{$w$ is not backtracking}\\}$ be the disjoint union of Euclidean
triangles of target triangles of walks starting at $T_{0}$. We can now define
$\hat{\Sigma}$ as $\hat{\mathcal{F}}/{\hat{\sim}}$, where for any two walks
$w$ and $w^{\prime}$, where $w^{\prime}$ is obtained from $w$ by removing its
final link, $\hat{\sim}$ glues $T_{w^{\prime}}$ to $T_{w}$ along the sides
corresponding to the last link of $w$. Let $q\colon\hat{\Sigma}\to\Sigma$ be
the map that sends points of $\hat{\Sigma}$ to their corresponding point in
$\Sigma$. A map $\hat{g}\colon X\to\hat{\Sigma}$ is a _lift_ of $g\colon
X\to\Sigma$ if $g=q\circ\hat{g}$. Any path $\pi\colon[0,1]\to\Sigma$ has a
lift $\hat{\pi}$ in $\hat{\Sigma}$.

There is a map $f\colon\hat{\Sigma}\to\mathbb{R}^{2}$ whose restriction to any
triangle of $\hat{\Sigma}$ is an isometry, and whose restriction to any pair
of adjacent triangles is injective. We can think of $f$ as unfolding
$\hat{\Sigma}$ so that it lies flat in the plane and is locally isometric
everywhere except at the vertices (vertices are the only source of curvature),
see Figure 12.

Figure 12: $\Sigma$ (left) and a local region of $\hat{\Sigma}$ (right). The
dual graph of $\hat{\Sigma}$ is an infinite tree (red).

Let $B_{r}(x,y)=\\{p\in\mathbb{R}^{2}\mid\|p-(x,y)\|<r\\}$ be the open disk in
the plane of radius $r$ centered at $(x,y)$. If a component $U$ of
$f^{-1}(B_{r}(x,y))$ contains no vertices, then the restriction of $f$ to the
closure of $U$ is an isometry.

For a triangle $T$ of $\hat{\Sigma}$, let $D(T)$ be the open disk bounded by
the circumcircle of $f(T)$, and let $C(T)$ be the closure of the component of
$f^{-1}(D(T))$ that contains the interior of $T$. A triangle $T$ of
$\hat{\Sigma}$ is _Delaunay_ if $C(T)$ does not contain any vertices of
triangles adjacent to $T$ in its interior. $\mathcal{T}$ is an _intrinsic
Delaunay triangulation_ of $\Sigma$ if and only if all triangles of
$\hat{\mathcal{F}}$ are Delaunay. Lemma 4.1 generalizes a well-known property
of Delaunay triangulations in the plane.

######  Lemma 4.1 (Bobenko et al. [4]).

If $\hat{\mathcal{T}}$ is an intrinsic Delaunay triangulation of
$\hat{\Sigma}$, then for any $T\in\hat{\mathcal{T}}$, $C(T)$ contains no
vertices in its interior.

Combining Observation 4.1 and Lemma 4.1, we obtain the following corollaries,
see also Figure 13.

######  Corollary 4.2.

For any triangle $T$ of an intrinsic Delaunay triangulation of $\hat{\Sigma}$,
the restriction of $f$ to $C(T)$ is injective, and shortest paths intersect
$C(T)$ in straight segments.

######  Corollary 4.3.

For any triangle $T$ of an intrinsic Delaunay triangulation of $\hat{\Sigma}$,
$\partial f(C(T))$ is a union of chords and circular arcs of $\partial D(T)$,
where each chord is a boundary edge.

Figure 13: Although $f$ is not injective in general, for a triangle $T$ of a
Delaunay triangulation, the restriction of $f$ to $C(T)$ is injective and
contains no vertices of the triangulation in the interior.

###  4.2 Intrinsic Delaunay triangulations are happy

We are now ready to prove the main result of this section: the intrinsic
Delaunay triangulation of any portalgon has constant happiness.

Let $\mathcal{T}$ be an intrinsic Delaunay triangulation of $\Sigma$. We want
to bound the number of intersections between a shortest path $\pi$ on $\Sigma$
and edges of the triangulation. For this, let $\pi$ be a shortest path between
two given points on $\Sigma$, and among all such paths, assume that $\pi$ has
a minimum number of crossings with edges of $\Sigma$. Here, we count crossings
with an edge as the components of intersection with that edge.

Now consider an arbitrary edge $e$ between two vertices $u$ and $v$ of the
triangulation and let $m$ be its midpoint. We will show that $\pi$ intersects
$e$ only constantly often. For a contradiction, suppose that $\pi$ intersects
$e$ at least $7$ times. If a component of intersection of $\pi$ with $e$ is
not transversal and does not contain a vertex, then it follows from Corollary
4.2 that $\pi$ is a segment of $e$, so $\pi$ has only one edge crossing. If a
non-transversal intersection contains both vertices of $e$, then $\pi$
contains $e$ and hence intersects $e$ only once. Thus, every non-transversal
intersection of $\pi$ with $e$ contains exactly one vertex of $e$, and hence
contains the start or end of $\pi$. Therefore, $\pi$ intersects $e$ non-
transversally at most twice.

To bound the total number of intersections with $e$ we analyze the geometry of
$\hat{\pi}$ in a local neighborhood of a lift $\hat{e}$ of $e$. Arbitrarily
fix one of the triangles $T$ incident to $e$ and consider the neighborhood
$C(\hat{T})$ of $\hat{e}$ for the corresponding lift $\hat{T}$ incident to
$\hat{e}$. By Corollary 4.2, the restriction of $f$ to $C(\hat{T})$ is an
isometry, so $f(\mathrm{Im}(\hat{\pi})\cap C(\hat{T}))$ is a straight line
segment. Let $p_{i}$ be the $i$-th point of (or vertex of non-transversal)
intersection of $\pi$ with $e$, and define $\lambda_{i}$ such that
$\pi(\lambda_{i})=p_{i}$. Let $\hat{e}_{i}$ be a lift of $e$ containing
$\hat{\pi}(\lambda_{i})$, and let $\hat{p}_{i}$, $\hat{T}_{i}$, $\hat{u}_{i}$,
$\hat{m}_{i}$, $\hat{v}_{i}$ be the respective lifts of $p_{i}$, $T$, $u$,
$m$, $v$ incident to $\hat{e}_{i}$, see Figure 14 (left). Let
$D_{i}:=D(\hat{T}_{i})$, and $f_{i}$ be the restriction of $f$ to
$C_{i}:=C(\hat{T}_{i})$. Let $c_{i}$ be the center of $D_{i}$, i.e., the
circumcenter of $f(\hat{T}_{i})$.

Figure 14: The crossing $p_{i}$ of $\pi$ with $e$ is inward.

Define $H_{i}^{I}$ and $H_{i}^{O}$ to be the two half-planes bounded by the
line through $f(\hat{e}_{i})$, such that $H_{i}^{I}$ contains $c_{i}$ (if
$c_{i}=f(\hat{m}_{i})$, label the half-planes by $H_{i}^{I}$ and $H_{i}^{O}$
arbitrarily). We respectively call $H_{i}^{I}$ and $H_{i}^{O}$ the _inner_ and
_outer_ half-plane of $\hat{e}_{i}$, and define
$C_{i}^{I}:=f_{i}^{-1}(H_{i}^{I})$ to be the _inner_ component of
$\hat{e}_{i}$, and $C_{i}^{O}:=f_{i}^{-1}(H_{i}^{O})$ to be the _outer_
component of $\hat{e}_{i}$.

We call the crossing $p_{i}$ _inward_ if $p_{i}$ is a non-transversal crossing
or $\hat{\pi}$ crosses $\hat{p}_{i}$ from $C_{i}^{O}$ to $C_{i}^{I}$, see
Figure 14 (right).

Let $s$ be the segment of $e$ from $u$ to $m$. Assume without loss of
generality that at least four of the (at least seven) crossings of $\pi$ with
$e$ lie on $s$ (otherwise relabel $u$ and $v$).

######  Lemma 4.4.

For any inward crossing $p_{i}$ of $\pi$ with $s$, none of the crossings
$p_{j}$ with $j>i$ lie on the segment of $s$ between $u$ and $p_{i}$.

######  Proof 4.5.

Suppose for a contradiction that for some $j>i$, $p_{j}$ lies on the segment
of $e$ between $u$ and $p_{i}$. Let $Z$ be the open disk centered at
$f(\hat{m}_{i})$ with $f(\hat{e}_{i})$ as diameter. The path
$\hat{m}_{i}\mathrel{\leavevmode\hbox to12.04pt{\vbox
to13.95pt{\pgfpicture\makeatletter\hbox{\hskip 6.01958pt\lower-7.52339pt\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{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.46681pt}{-2.9516pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\scriptstyle\hat{e}_{i}$}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}}{}{{}}{}{{}} {}{} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}} {{{{}{}{{}} }}{{}}
}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}{{}}} {{{{}{}{{}} }}{{}} {} }{{{{}{}{{}}
}}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}}
{{}} } {{{{}{}{{}} }}{{}}{{}}} {}{{
{\pgfsys@beginscope\pgfsys@setlinewidth{0.32pt}\pgfsys@setdash{}{0.0pt}\pgfsys@roundcap\pgfsys@roundjoin{}
{}{}{} {}{}{}
\pgfsys@moveto{-1.19998pt}{1.59998pt}\pgfsys@curveto{-1.09998pt}{0.99998pt}{0.0pt}{0.09999pt}{0.29999pt}{0.0pt}\pgfsys@curveto{0.0pt}{-0.09999pt}{-1.09998pt}{-0.99998pt}{-1.19998pt}{-1.59998pt}\pgfsys@stroke\pgfsys@endscope}}
}{}{}{{}}\pgfsys@moveto{5.35959pt}{-6.6234pt}\pgfsys@lineto{1.81958pt}{-6.6234pt}\pgfsys@lineto{0.966pt}{-7.3234pt}\pgfsys@lineto{-0.74117pt}{-5.9234pt}\pgfsys@lineto{-2.44833pt}{-7.3234pt}\pgfsys@lineto{-4.1555pt}{-5.9234pt}\pgfsys@lineto{-5.81958pt}{-6.6234pt}\pgfsys@lineto{-5.81958pt}{-6.6234pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{5.35959pt}{-6.6234pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\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}}}\hat{p}_{i}\mathrel{\leavevmode\hbox
to10.66pt{\vbox to12.63pt{\pgfpicture\makeatletter\hbox{\hskip
5.33055pt\lower-6.86388pt\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{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.77779pt}{-3.61111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\scriptstyle\hat{\pi}$}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}}{}{{}}{}{{}} {}{} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}} {{{{}{}{{}} }}{{}}
}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}{{}}} {{{{}{}{{}} }}{{}} {} }{{{{}{}{{}}
}}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {{}} } {{{{}{}{{}}
}}{{}}{{}}}
{}{}{}{}{{}}\pgfsys@moveto{4.67056pt}{-5.96388pt}\pgfsys@lineto{1.13055pt}{-5.96388pt}\pgfsys@lineto{0.27698pt}{-6.66388pt}\pgfsys@lineto{-1.43019pt}{-5.26389pt}\pgfsys@lineto{-3.13736pt}{-6.66388pt}\pgfsys@lineto{-5.13055pt}{-5.96388pt}\pgfsys@lineto{-5.13055pt}{-5.96388pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{4.67056pt}{-5.96388pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\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}}}\hat{p}_{j}\mathrel{\leavevmode\hbox
to12.54pt{\vbox to14.72pt{\pgfpicture\makeatletter\hbox{\hskip
6.26865pt\lower-7.91228pt\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{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.71588pt}{-2.56271pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\scriptstyle\hat{e}_{j}$}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}}{}{{}}{}{{}} {}{} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}} {{{{}{}{{}} }}{{}}
}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}{{}}} {{{{}{}{{}} }}{{}} {} }{{{{}{}{{}}
}}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}}
{{}} } {{{{}{}{{}} }}{{}}{{}}}
{}{}{}{}{{}}\pgfsys@moveto{5.60866pt}{-7.01228pt}\pgfsys@lineto{2.06865pt}{-7.01228pt}\pgfsys@lineto{1.21507pt}{-7.71228pt}\pgfsys@lineto{-0.4921pt}{-6.31229pt}\pgfsys@lineto{-2.19926pt}{-7.71228pt}\pgfsys@lineto{-3.90643pt}{-6.31229pt}\pgfsys@lineto{-6.06865pt}{-7.01228pt}\pgfsys@lineto{-6.06865pt}{-7.01228pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{5.60866pt}{-7.01228pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\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}}}\hat{u}_{j}$ is
strictly shorter than $s$, so the segment
$f(\hat{p}_{j}\mathrel{\leavevmode\hbox to12.54pt{\vbox
to14.72pt{\pgfpicture\makeatletter\hbox{\hskip 6.26865pt\lower-7.91228pt\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{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.71588pt}{-2.56271pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\scriptstyle\hat{e}_{j}$}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}}{}{{}}{}{{}} {}{} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}} {{{{}{}{{}} }}{{}}
}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}{{}}} {{{{}{}{{}} }}{{}} {} }{{{{}{}{{}}
}}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}}
{{}} } {{{{}{}{{}} }}{{}}{{}}}
{}{}{}{}{{}}\pgfsys@moveto{5.60866pt}{-7.01228pt}\pgfsys@lineto{2.06865pt}{-7.01228pt}\pgfsys@lineto{1.21507pt}{-7.71228pt}\pgfsys@lineto{-0.4921pt}{-6.31229pt}\pgfsys@lineto{-2.19926pt}{-7.71228pt}\pgfsys@lineto{-3.90643pt}{-6.31229pt}\pgfsys@lineto{-6.06865pt}{-7.01228pt}\pgfsys@lineto{-6.06865pt}{-7.01228pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{5.60866pt}{-7.01228pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\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}}}\hat{u}_{j})$ lies
interior to $Z$. Note that $H_{i}^{I}\cap Z$ lies completely inside $D_{i}$,
and hence does not contain any vertices of $C_{i}^{I}$ in its interior, so in
particular $\hat{u}_{j}$ does not lie in $C_{i}^{I}$. Moreover, any path that
enters the interior of $C_{i}^{I}$ cannot leave it without leaving $Z$ or
crossing the interior of $\hat{e}_{i}$ (because $\hat{e}_{i}$ is the only
common boundary of $C_{i}^{I}$ and $\hat{\Sigma}\setminus C_{i}^{I}$ that lies
inside $Z$). However, the path $\hat{p}_{i}\mathrel{\leavevmode\hbox
to10.66pt{\vbox to12.63pt{\pgfpicture\makeatletter\hbox{\hskip
5.33055pt\lower-6.86388pt\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{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.77779pt}{-3.61111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\scriptstyle\hat{\pi}$}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}}{}{{}}{}{{}} {}{} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}} {{{{}{}{{}} }}{{}}
}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}{{}}} {{{{}{}{{}} }}{{}} {} }{{{{}{}{{}}
}}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {{}} } {{{{}{}{{}}
}}{{}}{{}}}
{}{}{}{}{{}}\pgfsys@moveto{4.67056pt}{-5.96388pt}\pgfsys@lineto{1.13055pt}{-5.96388pt}\pgfsys@lineto{0.27698pt}{-6.66388pt}\pgfsys@lineto{-1.43019pt}{-5.26389pt}\pgfsys@lineto{-3.13736pt}{-6.66388pt}\pgfsys@lineto{-5.13055pt}{-5.96388pt}\pgfsys@lineto{-5.13055pt}{-5.96388pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{4.67056pt}{-5.96388pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\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}}}\hat{p}_{j}\mathrel{\leavevmode\hbox
to12.54pt{\vbox to14.72pt{\pgfpicture\makeatletter\hbox{\hskip
6.26865pt\lower-7.91228pt\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{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.71588pt}{-2.56271pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\scriptstyle\hat{e}_{j}$}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}}{}{{}}{}{{}} {}{} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}} {{{{}{}{{}} }}{{}}
}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}{{}}} {{{{}{}{{}} }}{{}} {} }{{{{}{}{{}}
}}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}}
{{}} } {{{{}{}{{}} }}{{}}{{}}}
{}{}{}{}{{}}\pgfsys@moveto{5.60866pt}{-7.01228pt}\pgfsys@lineto{2.06865pt}{-7.01228pt}\pgfsys@lineto{1.21507pt}{-7.71228pt}\pgfsys@lineto{-0.4921pt}{-6.31229pt}\pgfsys@lineto{-2.19926pt}{-7.71228pt}\pgfsys@lineto{-3.90643pt}{-6.31229pt}\pgfsys@lineto{-6.06865pt}{-7.01228pt}\pgfsys@lineto{-6.06865pt}{-7.01228pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{5.60866pt}{-7.01228pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\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}}}\hat{u}_{j}$ enters
and leaves $C_{i}^{I}$ without leaving $Z$. The path
$\hat{p}_{i}\mathrel{\leavevmode\hbox to10.66pt{\vbox
to12.63pt{\pgfpicture\makeatletter\hbox{\hskip 5.33055pt\lower-6.86388pt\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{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.77779pt}{-3.61111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\scriptstyle\hat{\pi}$}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}}{}{{}}{}{{}} {}{} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}} {{{{}{}{{}} }}{{}}
}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}{{}}} {{{{}{}{{}} }}{{}} {} }{{{{}{}{{}}
}}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {{}} } {{{{}{}{{}}
}}{{}}{{}}}
{}{}{}{}{{}}\pgfsys@moveto{4.67056pt}{-5.96388pt}\pgfsys@lineto{1.13055pt}{-5.96388pt}\pgfsys@lineto{0.27698pt}{-6.66388pt}\pgfsys@lineto{-1.43019pt}{-5.26389pt}\pgfsys@lineto{-3.13736pt}{-6.66388pt}\pgfsys@lineto{-5.13055pt}{-5.96388pt}\pgfsys@lineto{-5.13055pt}{-5.96388pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{4.67056pt}{-5.96388pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\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}}}\hat{p}_{j}$ does not
repeatedly cross $\hat{e}_{i}$, so the segment of $\hat{e}_{j}$ between
$\hat{p}_{j}$ and $\hat{u}_{j}$ must cross $\hat{e}_{i}$, so $\hat{e}_{j}$
crosses the interior of $\hat{e}_{i}$, but this is a contradiction because
edges of the triangulation are interior-disjoint.

If $p_{i}$ of $\pi$ is not inward, then it is inward on the reverse of $\pi$.
Corollary 4.6 follows.

######  Corollary 4.6.

If some crossing $p_{i}$ of $\pi$ with $s$ is not inward, then none of the
crossings $p_{h}$ with $h<i$ lie on the segment of $s$ between $u$ and
$p_{i}$.

Figure 15: A subsequence of crossings $p_{h}$, $p_{i}$, $p_{j}$ of $\pi$ with
$s$ whose distance from $u$ is increasing.

Lemma 4.4 implies that for the sequence of intersections $p_{i}$ of $\pi$ with
$s$, the distance function from $u$ to $p_{i}$ along $s$ has only one local
minimum. So there exists a subsequence of at least three crossings $p_{h}$,
$p_{i}$ and $p_{j}$ ($h<i<j$) of $\pi$ with $s$ such that $p_{i}$ lies between
$p_{h}$ and $p_{j}$. Assume without loss of generality that the distances
(along $s$) from $u$ to $p_{h}$, $p_{i}$, and $p_{j}$ are increasing (the
other case follows by considering the reverse of $\pi$). At this point, we
observe: $f(\hat{m}_{i})\neq c_{i}$

######  Proof 4.7.

Suppose for contradiction that $f(\hat{m}_{i})$ is $c_{i}$. In that case we
labeled $H_{i}^{I}$ and $H_{i}^{O}$ arbitrarily, and the other labeling tells
us that the distances from $u$ to $p_{h}$, $p_{i}$, and $p_{j}$ must be
decreasing instead of increasing, which is impossible if they were increasing
to begin with (switching the labeling does not change the distances from $u$).

By Corollary 4.6, $p_{i}$ is an inward crossing. We show how the possible
locations of the subsequent crossings inside $C_{i}$ are constrained. Define
$D^{\prime}_{i}$ to be the disk concentric with $D_{i}$, whose boundary passes
through $f(\hat{m}_{i})$. Any chord of $D_{i}$ that passes through
$D^{\prime}_{i}$ is at least as long as $e$. Let
$\overline{e}_{h}:=f(\hat{e}_{h})\cap D_{i}$. We observe:

######  Lemma 4.8.

$\overline{e}_{h}$ cannot intersect the closure of $D^{\prime}_{i}$.

######  Proof 4.9.

Let $R_{i}$ (shaded in Figure 16 (left)) be the interior of the convex hull of
$D^{\prime}_{i}\cup f(\hat{e}_{i})$. Because $C_{i}$ has no interior vertices,
no lift of $e$ intersects $f_{i}^{-1}(R_{i})$, see Figure 16 (left). In
correspondence with the figures, we will without loss of generality assume
that $f(\hat{e}_{i})$ is vertical, with $f(\hat{u}_{i})$ on the bottom, and
$H_{i}^{O}$ on the left.

Figure 16:  (Left) There is no lift of $e$ that intersects the interior of the
shaded region $R_{i}$ of $C_{i}$. (Middle) $\hat{p}_{j}$ lies in the blue
region, $\hat{p}_{h}$ in the green region. (Right) $\hat{u}_{h}$ cannot lie
interior to $C_{i}$.

The fact that the subsequent intersection $p_{j}$ of $\pi$ with $e$ lies on
the segment of $e$ between $p_{i}$ and $m$ constrains the angle at which $\pi$
can intersect $p_{i}$. Indeed, $f\circ\pi$ must leave $R_{i}$ before the next
intersection, and the distance from $\hat{p}_{i}$ to $\hat{p}_{j}$ is less
than that from $f(\hat{p}_{i})$ to $f(\hat{m}_{i})$. Figure 16 (middle)
illustrates the possible locations of $\hat{p}_{j}$. Crucially, the chord
(call it $\overline{\pi}$) of $D_{i}$ that contains $f(\hat{\pi}\cap C_{i})$
does not intersect $D^{\prime}_{i}$.

Because $f(\hat{m}_{i})\neq c_{i}$, two chords of $D_{i}$ pass through
$f(\hat{p}_{i})$ and are tangent to $D^{\prime}_{i}$. One of those chords is
$f(\hat{e}_{i})$, and the other chord (call it $\omega$) has one endpoint
(call it $w$) interior to $H_{i}^{O}$. Because $\overline{\pi}$ does not
intersect $D^{\prime}_{i}$, the point $f(\hat{p}_{h})$ lies on or above the
line through $w$ and $f(\hat{p}_{i})$. Then $\overline{e}_{h}$ is a chord of
$D_{i}$, and it cannot intersect the closure of $D^{\prime}_{i}$.

We will arrive at a contradiction to our initial assumption by showing:

######  Lemma 4.10.

If $\pi$ crosses $e$ at least $7$ times then $\overline{e}_{h}$ must intersect
the closure of $D^{\prime}_{i}$.

######  Proof 4.11.

Let $q\in\partial D_{i}$ be the point of $\overline{e}_{h}$ closest to
$f(\hat{u}_{h})$. We will analyze the possible locations of $q$. Let $d_{i}$
be the distance from $f(\hat{p}_{i})$ to $f(\hat{u}_{i})$. Let $B_{i}$ be the
disk of radius $d_{i}$ centered at $f(\hat{p}_{i})$, so that $B_{i}$
intersects $\partial D_{i}\cap H_{i}^{O}$ in the arc (labeled $\alpha$ in
Figure 16) connecting $w$ and $f(\hat{u}_{i})$. Let $b$ be the point inside
$H_{i}^{O}$ where $\overline{\pi}$ intersects $\partial B_{i}$. Let $B_{h}$ be
the disk centered at $f(\hat{p}_{h})$ whose boundary intersects $b$, so that
$B_{h}\subseteq B_{i}$. Let $d_{s}(\cdot,\cdot)$ be the distance along $s$,
then $q$ lies in $B_{h}$ because

$d(q,f(\hat{p}_{h}))\leq d_{s}(u,p_{h})=d_{s}(u,p_{i})-d_{s}(p_{i},p_{h})\leq
d_{s}(u,p_{i})-d(f(\hat{p}_{h}),f(\hat{p}_{i}))=d(b,f(\hat{p}_{h})).$

Thus, $q$ lies on the arc (call it $\gamma$) in which $B_{h}$ intersects
$\partial D_{i}\cap H_{i}^{O}$. This arc lies on the arc between
$f(\hat{u}_{i})$ and $w$. Let $\gamma_{0}$ be the point of $\gamma$ closest to
$w$, $\gamma_{1}$ be the point closest to $f(\hat{u}_{i})$, and
$\gamma_{\frac{1}{2}}$ be the midpoint of $\gamma$, see Figure 17. The line
through $\gamma_{\frac{1}{2}}$ and $f(\hat{p}_{h})$ passes through the center
$c_{i}$ of $D^{\prime}_{i}$, so the chord $\overline{e}_{h}$ intersects the
vertical line through $c_{i}$ at or below $c_{i}$.

Figure 17: Any chord of $D_{i}$ through $f(\hat{p}_{h})$ and $\gamma$
intersects $D^{\prime}_{i}$.

We distinguish two cases, first consider the case where $q$ lies on the arc of
$\gamma$ between $\gamma_{0}$ and $\gamma_{\frac{1}{2}}$. Note that
$\overline{e}_{h}$ is the chord of $D_{i}$ that passes through $q$ and
$f(\hat{p}_{h})$. Because $f(\hat{p}_{h})$ lies on or above $\omega$, the
segment of $\overline{e}_{h}$ from $q$ to $f(\hat{p}_{h})$ either coincides
with $\omega$ or intersects $\omega$ from below, so the remainder of
$\overline{e}_{h}$ coincides with $\omega$, or lies above $\omega$. In
particular, $\overline{e}_{h}$ lies above the point where $\omega$ is tangent
to $D^{\prime}_{i}$. However, any such line that also passes on or below
$c_{i}$ must intersect $D^{\prime}_{i}$, so $\overline{e}_{h}$ intersects
$D^{\prime}_{i}$ if $q$ lies on the arc of $\gamma$ between $\gamma_{0}$ and
$\gamma_{\frac{1}{2}}$.

The case where $q$ lies on the arc between $\gamma_{\frac{1}{2}}$ and
$\gamma_{1}$ follows by the symmetry of $D^{\prime}_{i}$, $f(\hat{p}_{h})$,
and $\gamma$ after reflection through the line through $f(\hat{p}_{h})$ and
$c_{i}$. Hence, the chord $\overline{e}_{h}$ intersects $D^{\prime}_{i}$.

By Lemma 4.10 the chord $\overline{e}_{h}$ intersects $D^{\prime}_{i}$, which
is a contradiction. We conclude that $\pi$ intersects $e$ at most six times.
We summarize our discussion in the following theorem.

######  Theorem 4.12.

Let $\mathcal{P}$ be a portalgon with $n$ vertices. There exists a portalgon
$\mathcal{P}^{\prime}\equiv\mathcal{P}$ with $O(n)$ vertices that is
$O(1)$-happy.

##  5 Making portalgons happy

In this section we study conditions for a fragment to be happy, and we present
a method to rearrange an unhappy fragment into an equivalent one that is
happy.

We start observing that the approach from Section 4 is, in principle,
constructive. However, its running time depends on the number of edge flips
required to reconfigure an initial triangulation of the fragments into the
intrinsic Delaunay triangulation, and this number may not be expressible in
terms of the input complexity. Whether the intrinsic Delaunay triangulation
can be computed in a different way is an open question. We note that when
there is a bound on the minimum angle on the input triangles, the number of
flips can be bounded [18].

The rest of this section is devoted to an analysis of what we can do when
there is no such minimum angle bound. The main result in this section is that
we can reduce any portalgon for which the fragment graph contains at most one
cycle to the case of a portalgon with just one fragment and a single portal,
which we can rearrange to have only fragments of constant happiness (Theorem
5.36).

We begin with a simple observation that will be useful.

Any fragment $F$ with at most one portal edge $e$ is $2$-happy.

######  Proof 5.1.

Assume by contradiction that $F$ is not 2-happy. Then there must be two points
$p,q\in\mathcal{P}$ for which $\pi(p,q)$ crosses $e$ at least three times, and
thus there is a subpath $\pi(r,s)$ of $\pi(p,q)$ such that: $r$ and $s$ lie on
$e$, $\pi(r,s)\subseteq F$, and $\pi(r,s)$ contains a point in the interior of
$F$. By triangle inequality $\overline{rs}$ is then shorter than $\pi(r,s)$.
Contradiction.

We now consider the situation in which there is only a single portal, and give
a constructive result on how to compute an equivalent happy portalgon. First,
we focus on the easier case where the two portal edges are parallel. In
Appendix 5.2 we extend this result to non-parallel edges. We also note there
that if the angle between the two edges is at least a constant, then the
fragment is already happy. Thus the near-parallel case is of most interest.

###  5.1 Single portal, parallel edges

####  5.1.1 Analysis

The happiness of a fragment with a single portal depends on the shift of the
two (parallel) portal edges. The shift of two portal edges ${e^{-}},{e^{+}}$
can be defined as the distance between the two perpendiculars to the portal
edges that go through the start vertices of ${e^{-}}$ and ${e^{+}}$,
respectively. In the following we assume without loss of generality that the
portals are horizontal, thus the shift $\Delta$ is simply the difference in
$x$-coordinate between the start vertices of the portal edges. Further, let
$v$ denote the vertical distance between ${e^{-}}$ and ${e^{+}}$.

######  Lemma 5.2.

Let $F$ be a fragment with exactly two portal edges ${e^{-}},{e^{+}}$, which
are parallel and belong to the same portal. If the shift $\Delta$ of
${e^{-}},{e^{+}}$ is $0$, then the fragment is $2$-happy.

######  Proof 5.3.

Let $F$ be a fragment with two parallel portal edges ${e^{-}},{e^{+}}$ with a
shift of $\Delta=0$, and recall that ${e^{-}}$ and ${e^{+}}$ are assumed to be
horizontal.

Suppose that there are two points $p,q\in F$ whose shortest path crosses
${e^{-}}$ (and thus also ${e^{+}}$) twice, say first at point $r$ and then at
$s$. Consider the subpath of the shortest path from ${r^{+}}$ to $s$. This
subpath must have length at least $|{r^{+}}s|$. Since $e$ and $e^{\prime}$ are
parallel and $\Delta=0$, $\triangle r{r^{+}}s$ has a right angle at $r$ and
${r^{+}}s$ is its hypotenuse, hence $|{r^{+}}s|>|{r^{-}}s|$. Thus going from
$r$ to $s$ along $e$ is shorter, reaching a contradiction. It follows that $F$
is $2$-happy.

If $\Delta\neq 0$, a fragment might be happy or not, depending on several
other circumstances: the length of the portals, the distance between the
portal edges, and whether the boundary of $F$ interferes or not. In the
following we present a method to transform a fragment that is not happy into
an equivalent portalgon that is happy.

The general idea is to create a new portal by cutting $F$ through a line in
the direction orthogonal to the line through the two start vertices of the
portals.

First we present the idea for the case where $F$ is a parallelogram; we refer
to its two parallel portal edges by ${e^{-}}$ and ${e^{+}}$.

Assume without loss of generality that ${e^{-}}$ is above ${e^{+}}$, and that
${e^{-}}$ starts to the left of ${e^{+}}$. In this case, the slope of the line
in the direction orthogonal to the portal start points is $z=-\Delta/v$. We
begin at the leftmost vertex of ${e^{+}}$, and shoot a ray with slope $z$ in
the inside of $F$ until we hit the boundary. Every time the ray crosses the
portal, we “cut” along this ray, creating a new portal along it. This results
in several smaller fragments, which we then glue together again along the
pieces of the original portals, into a fragment. The resulting fragment is a
rectangle $F^{\prime}$. See Figure 18 for an illustration. Note that, by
definition of $z$, this new fragment $F^{\prime}$ now has shift zero. Hence:

######  Lemma 5.4.

For any parallelogram with two parallel portal edges, there is an equivalent
parallelogram that has $\Delta=0$ and therefore is $2$-happy.

Figure 18: Left: a fragment with two parallel edges and non-zero shift.
Center: result of cutting the fragment along a perpendicular ray, resulting in
a new fragment with several portals, which is equivalent to a fragment with
one portal and zero shift (right).

Note that for a fragment with two parallel portals and non-zero shift, there
is a unique equivalent fragment with zero shift, which is the one obtained by
cutting along the perpendicular ray. However, if $F$ is not a parallelogram,
it may occur that when gluing together the new smaller fragments we obtain a
non-simple polygon. Therefore we may not be able to transform $F$ into a
single equivalent $h$-happy fragment, as shown in the example in Figure 19. In
that case, cutting along the perpendicular ray produces a non-simple fragment.

Figure 19: Example of a fragment (left) where the technique of cutting along
the perpendicular ray produces a non-simple polygon (center). However, this
can be fixed by using one more fragment (right).

There exists a fragment with two horizontal portal edges for which there is no
equivalent single fragment with $\Delta=0$.

Fortunately, we can transform any fragment with two parallel portal edges into
a constant number of $h$-happy fragments. First, we make a useful observation.

######  Lemma 5.5.

Consider a fragment $F$ with two horizontal portals ${e^{-}}$ and ${e^{+}}$.
Let $m$ be the line through the start points of ${e^{-}}$ and ${e^{+}}$. If
there is no line segment parallel to $m$ from a point on ${e^{-}}$ to a point
on ${e^{+}}$ whose interior lies in the interior of $F$, then $F$ is
$5$-happy.

######  Proof 5.6.

Figure 20: Illustration of the proof of Lemma 5.5; $\pi$ is shown in brown.
The segment ${p_{3}^{-}}{p_{3}^{+}}$ is parallel to $m$ and is fully contained
in the fragment.

Suppose that $F$ is not $5$-happy. Then there is a shortest path $\pi$ whose
intersection with $F$ consists of at least six connected components, and thus
$\pi$ crosses the portal at least five times, in points $p_{1},\ldots,p_{5}$.
See Figure 20. Since $\pi$ is a shortest path, these components cannot share
vertices (otherwise we could simply shorten the path). It follows that
$\pi({p_{2}^{+}},{p_{3}^{-}})$ must be a line segment (otherwise, if it would
include a vertex from $F$, such a vertex would be shared with
$\pi({p_{1}^{+}},{p_{2}^{-}})$ or with $\pi({p_{3}^{+}},{p_{4}^{-}})$).
Analogously, $\pi({p_{3}^{+}},{p_{4}^{-}})$ must be a line segment.
Furthermore, $\pi({p_{2}^{+}},{p_{3}^{-}})$ and $\pi({p_{3}^{+}},{p_{4}^{-}})$
are parallel, and thus ${p_{2}^{+}}{p_{3}^{-}}{p_{4}^{-}}{p_{3}^{+}}$ is an
empty parallelogram. Observe that, since ${p_{3}^{-}}$ and ${p_{3}^{+}}$ are
corresponding points (i.e., twins), the segment between them has the same
slope as $m$. Therefore, there is a line segment parallel to $m$ whose
interior is inside $F$.

If there is a segment parallel to $m$ contained in $F$ connecting ${e^{-}}$ to
${e^{+}}$, then in particular there is also a leftmost and a rightmost such
segment (we consider here $F$ as a closed set). These segments, together with
the pieces of portal edges, form an empty parallelogram. Let $Z$ be this
parallelogram, bounded by two horizontal edges and two edges parallel to $m$.

Let $F$ be a simple fragment, let $\overline{ab}$ be a line segment inside
$F$. A single connected component $\pi\cap F$ of a shortest path $\pi$ can
intersect $\overline{ab}$ in at most one segment.

In particular, Observation 5.1.1 implies that the two endpoints $p$ and $q$ of
a maximal component of $\pi\cap F$ cannot lie on the same portal edge $e$
unless $\pi(p,q)=\overline{pq}$.

######  Lemma 5.7.

Let $\mathcal{P}$ be a portalgon with one fragment $F$ with $n$ vertices, and
one portal whose edges are parallel. There exists a $5$-happy portalgon
$\mathcal{P}^{\prime}$ equivalent to $\mathcal{P}$ consisting of at most three
fragments and total complexity $O(n)$.

######  Proof 5.8.

Assume without loss of generality that both portal edges ${e^{-}}$ and
${e^{+}}$ are horizontal and oriented left-to-right. We now argue that when no
three vertices of $F$ are colinear, and $F$ is not already $5$-happy, we can
split $F$ into at most seven $4$-happy fragments of total complexity $O(n)$.
Refer to Figure 21. Finally, we show how to reduce the number of fragments to
three, while remaining $4$-happy, even without the general position
assumption.

Let $m$ be the line through the start points of ${e^{-}}$ and ${e^{+}}$. By
Lemma 5.5, if there is no translate of $m$ whose intersection with $F$
contains a segment connecting ${e^{-}}$ to ${e^{+}}$, $F$ is already
$5$-happy. Let $m_{\ell}$ be the leftmost such translate of $m$ and $m_{r}$
the rightmost such translate; $m_{\ell}$ contains a vertex $\ell$ of $F$ and
$m_{r}$ contains a vertex $r$ of $F$ (possibly, $\ell$ or $m$ is an endpoint
of ${e^{-}}$ or ${e^{+}}$). Let ${a^{-}}$ and ${a^{+}}$ be the intersection
points of $m_{\ell}$ with ${e^{-}}$ and ${e^{+}}$, and let ${b^{-}}$ and
${b^{+}}$ be the intersection points of $m_{r}$ with ${e^{-}}$ and ${e^{+}}$.
We cut the parallelogram $Z={a^{-}}{b^{-}}{a^{+}}{b^{+}}$ from $F$, which
splits $F$ into at most seven fragments (since, by general position,
$\overline{{a^{-}}{a^{+}}}$ and $\overline{{b^{-}}{b^{+}}}$ contain at most
two reflex vertices each). We now transform $Z$ into a $2$-happy fragment
using Lemma 5.4. Let $T$ and $B$ be the fragments containing the starting
points of ${e^{-}}$ and ${e^{+}}$, respectively. We argue that $T$ is
$4$-happy. The argument that $B$ is $4$-happy is symmetric. The same holds for
the fragments containing the endpoints of ${e^{-}}$ and ${e^{+}}$. Any other
fragments (if they exist) contain only one portal edge and are thus $2$-happy
by Observation 5.

Figure 21:  (a) Fragment $F$ with two parallel portals. (b) The lines
$m_{\ell}$ and $m_{r}$ intersecting ${e^{-}}$ and ${e^{+}}$ in
${a^{-}},{a^{+}}$ define a parallelogram $Z={a^{-}}{b^{-}}{a^{+}}{b^{+}}$ that
splits $F$ into at most seven sub fragments. (c) The resulting set of
$5$-happy fragments. Note that it is possible to reduce the number of
fragments by shifting $m_{\ell}$ slightly to the right and $m_{r}$ slightly to
the left.

Consider the maximal connected components of a shortest path $\pi=\pi(s,t)$
with $F$. By Observation 5.1.1 such a component either: (i) contains $s$, (ii)
contains $t$, or (iii) connects a point $p_{i}$ on ${e^{-}}$ to a point
$q_{i}$ on ${e^{+}}$. Again by Observation 5.1.1 each such component can
intersect $\overline{{a^{-}}{a^{+}}}$ at most once, so each such component can
intersect $T$ at most once.

We now further classify the type (iii) components into three types, depending
on whether $p_{i}$ lies on the part of ${e^{-}}$ in $T$ and whether $q_{i}$
lies on the part of ${e^{+}}$ in $B$.

If $p_{i}$ lies outside $T$, then Observation 5.1.1 implies that
$\pi(p_{i},q_{i})$ does not intersect (the interior of) $T$ at all since
$\pi(p_{i},q_{i})$ would have to intersect $\overline{a\ell}$ twice.

If $p_{i}$ lies in $T$ and $q_{i}$ lies in $B$, then Observation 5.1.1 implies
that $\pi(p_{i},q_{i})$ contains point $\ell$. Hence, there can be at most one
such component of this type that intersects $T$.

If $p_{i}$ lies in $T$ but $q_{i}$ lies outside of $B$, we have that
$q_{i}={t^{+}}$ for some point ${t^{-}}$ on $e$. If the component starting in
${t^{-}}$ is again of type (iii) (i.e., ${t^{-}}=p_{i+1}$) it cannot intersect
$B$ as this would imply that $\pi(p_{i+1},q_{i+1})$ intersects
$\pi(p_{i},q_{i})$. Nor can it intersect $T$ (since $q_{i+1}$ lies on
${e^{+}}$ it would have to intersect $\overline{a\ell}$ twice). The same
argument holds for any component on $\pi(p_{j},q_{j})$ with $j>i$. Hence,
$\pi(p_{i},q_{i})$ intersects $T$ only if this is the last component of type
(iii). Clearly, there is only one such a component.

It follows that there are only four components of $\pi\cap F$ that intersect
$T$, and each such component intersects $T$ in only one consecutive subpath.
Hence $T$ is $4$-happy.

We conclude that the portalgon $\mathcal{P}$’ that we obtain is $4$-happy,
equivalent to $\mathcal{P}$, and has at most seven fragments (note that there
will be seven fragments if there are two reflex vertices on $m_{\ell}$, and
two on $m_{r}$). Furthermore, every vertex of $\mathcal{P}$ appears in at most
$O(1)$ fragments of $\mathcal{P}^{\prime}$, and thus $\mathcal{P}^{\prime}$
has complexity $O(n)$.

Finally, observe that (before splitting $F$) we can actually shift the left
and right sides of $Z$ inwards by some arbitrarily small $\varepsilon$ (in
particular, something smaller than the smallest distance between two non-
adjacent edges of $Z$). It then follows that $F$ is now split into only three
fragments, two of which are already $4$-happy. We transform the remaining
fragment (parallelogram $Z$) into a $2$-happy parallelogram as before. We now
obtain three fragments, of total complexity $O(n)$), even if $F$ contains
three or more colinear vertices.

####  5.1.2 Computation

The previous analysis leads to an algorithm, as we show next. In the
following, recall that $z$ is the slope of a line orthogonal to the line
through the two start points of the portal edges.

######  Lemma 5.9.

Let $F$ be a parallelogram with two parallel portal edges, we can compute an
equivalent $2$-happy parallelogram $F^{\prime}$ in $O(1)$ time.

######  Proof 5.10.

By Lemma 5.4 there exists a parallelogram $F^{\prime}$ equivalent to $F$ that
has shift zero, and is thus $2$-happy. The main task is now to compute such an
equivalent fragment.

To compute the new, equivalent fragment $F^{\prime}$, we could explicitly
generate the ray $\rho$, and compute its intersection points with the portal
edges, tracing the ray until it hits a non-portal edge of the fragment. See
Figure 22(a). However, this would result in a running time linear in the
number of such intersections. Instead, we can compute the resulting fragment
directly, by exploiting the geometry of the situation.

Let $b_{l}$ be the line segment between the left endpoints of ${e^{-}}$ and
${e^{+}}$, and let $b_{r}$ be defined analogously for the right endpoints of
${e^{-}}$ and ${e^{+}}$. See Figure 22(b). We observe that since the ray
$\rho$ is orthogonal to $b_{l}$, the total length of the ray until it hits a
fragment edge is the same as the distance $|\rho|$ between the two parallel
lines that go through $b_{l}$ and $b_{r}$, respectively. See Figure 22(b).
After cutting along the ray and gluing the pieces together, the zero-shift
guarantees that the resulting shape is a rectangle. The rectangle has $b_{l}$
as base, and has height equal to the length of the ray until hitting $t$,
$|\rho|$. This rectangle can be computed in $O(1)$ time by considering the
supporting lines of ${e^{-}}$ and ${e^{+}}$, and intersecting them with two
orthogonal lines going through the endpoints of $b_{l}$; refer to the dashed
rectangle in Figure 22(b). The four intersections of these four lines give the
vertices of the rectangle, which is the equivalent 2-happy portalgon.

Figure 22: Cutting procedure for two parallel portals. (a) Initial situation.
(b) The resulting happy portalgon is the rectangle indicated with dashes.

Next we address the case where the fragment is not a parallelogram.

######  Lemma 5.11.

Let $F$ be a simple fragment containing two horizontal portal edges ${e^{-}}$
and ${e^{+}}$, and let $z$ be a slope. In $O(n_{F})$ time we can compute the
leftmost segment $s_{\ell}$ and the rightmost segment $s_{r}$ with slope $z$
with one endpoint on ${e^{-}}$ and one endpoint on ${e^{+}}$, or report that
no such segment exists.

######  Proof 5.12.

Assume without loss of generality that the portal edges
${e^{-}}=\overline{pq}$ and ${e^{+}}=\overline{st}$ are oriented from left to
right, with ${e^{-}}$ above ${e^{+}}$. Let $S$ be the parallelogram defined by
${e^{-}}$ and ${e^{+}}$, and let $X$ denote the part of the boundary of $F$,
excluding the interior of ${e^{-}}$ and ${e^{+}}$ intersecting $S$, i.e.
$X=S\cap(\partial F\setminus({e^{-}}\cup{e^{+}}\setminus\\{p,q,s,t\\}))$.
Since $F$ is simple, $X$ is a collection of polygonal chains. There are three
types of chains, depending on their endpoints: A chain is of type $L$ if its
endpoints lie on the left boundary $\overline{ps}$ of $S$, of type $R$ if its
endpoints lie on the right boundary $\overline{qt}$ of $S$, and of $M$ if one
of its endpoints lies on $\overline{ps}$ and one of its endpoint lies on
$\overline{qt}$. Clearly, if there are any chains of type $M$, the segments
$s_{\ell}$ and $s_{r}$ do not exist.

Observe that $s_{\ell}$, if it exists, contains a vertex of $F$ on a chain of
type $L$. In particular, let $\ell$ be the vertex on such a chain for which
the line $m_{\ell}$ through $\ell$ with slope $z$ is rightmost (note that
there is a well-defined order, since all lines with slope $z$ are parallel
(and $z\neq 0$)). Segment $s_{\ell}$ contains $\ell$. Symmetrically, $s_{r}$,
if it exists, contains the vertex $r$ on a chain of type $R$ whose line
$m_{r}$ is leftmost.

Finally, observe that if $s_{\ell}$ exists, the line $m_{\ell}$ must be left
of the line $m_{r}$. Conversely, if $m_{\ell}$ does not lie left of $m_{r}$,
$s_{\ell}$ does not exist.

We can compute the chains in $X$, and their type, in linear time by traversing
the boundary of $F$. Computing $\ell$ and $r$ can again be done in linear
time. Given $\ell$ and $r$, we can then decide if $s_{\ell}$ and $s_{r}$
exist, and, if they do, we can compute them in constant time.

######  Lemma 5.13.

Let $\mathcal{P}=(\mathcal{F},P)$ be a portalgon with $n$ vertices and only
one portal, whose edges are parallel. An equivalent $2$-happy portalgon
$\mathcal{P}^{\prime}$ with $|\mathcal{F}|+6$ fragments and total complexity
$O(n)$ can be computed in $O(n)$ time.

######  Proof 5.14.

We implement the constructive proof of Lemma 5.7 using Lemmas 5.11 and 5.9.
There is at most one fragment $F$ with two portal edges ${e^{-}}$ and
${e^{+}}$, both of which are parallel. We use Lemma 5.11 to find two parallel
segments whose endpoints lie on ${e^{-}}$ and ${e^{+}}$. If such segments do
not exist, $F$ is already 2-happy and we are done. Otherwise, they define a
parallelogram $Z$ that splits $F$ into at most seven pieces, one of which is
$Z$ itself. By Lemma 5.11, computing $Z$ takes linear time, as does the actual
splitting. We then use Lemma 5.9 to transform $Z$ into a 2-happy parallelogram
in $O(1)$ time. All fragments apart from $Z$ are already $2$-happy.

###  5.2 Single portal, arbitrary edges

We extend the results from Section 5.1 to non-parallel edges. Most of the
arguments are similar.

####  5.2.1 Analysis

For two portal edges that are not parallel, the situation does not change too
much. First, we analyze which orientations are actually problematic. There is
a clear relation between the angle between the portal edges, defined as the
angle of their corresponding supporting lines, and the number of times that a
shortest path can use it.

A fragment with angle $\alpha>0$ between the two portal edges is
$(\lfloor\pi/\alpha\rfloor+1)$-happy.

######  Proof 5.15.

In every iteration the angle of the shortest path with respect to one of the
portals increases by $\alpha$, or in every iteration it decreases by $\alpha$.
Therefore, if after $\lfloor\pi/\alpha\rfloor$ iterations the shortest path
would go through the portal again, it would have covered an angle of more than
$\pi$ in the interior of the fragment, which is not possible. Therefore, no
more iterations are possible. It follows that the shortest path can have at
most ($\lfloor\pi/\alpha\rfloor$+1) connected components in the fragment.

It is worth pointing out that, as soon as the angle $\alpha<\pi/2$, it is
possible to construct a situation where a shortest path goes through the
portal three times. See Figure 23 for an example where we make the start point
of the non-horizontal portal almost touch the horizontal portal; the orange
path is a shortest path.

Figure 23: Example for $\alpha=\pi/3<\pi/2$ where a shortest path (shown
orange) goes through the portal three times.

For small $\alpha$, the situation looks quite similar to the one with parallel
edges, with some important differences. Let $\Delta$ be the shift of the
portals, defined now as the distance between the projections of the starting
vertices of the two portal edges onto the _bisector_ of the portal edges,
where the bisector is the angle bisector of the supporting lines of the edges.

The following result generalizes Lemma 5.2.

######  Lemma 5.16.

Let $F$ be a fragment with exactly two portal edges ${e^{-}},{e^{+}}$ that
belong to the same portal. If the shift of ${e^{-}},{e^{+}}$ is $0$, then the
fragment is $2$-happy.

######  Proof 5.17.

Let $F$ be a fragment with two portal edges ${e^{-}},{e^{+}}$ with $\Delta=0$.
Assume without loss of generality that the associated angular bisector is
horizontal, and that ${e^{-}}$ is above ${e^{+}}$. Refer to Figure 24. Suppose
there are two points $p,q\in F$ whose shortest path crosses $e$ twice, say at
points $r$ and $s$, in the order ${r^{-}}$, ${r^{+}}$, ${s^{-}}$, ${s^{+}}$.
Consider the part of the shortest path from ${r^{+}}$ to ${s^{-}}$. Since
$\Delta=0$, this path must have length at least $|{r^{+}}{s^{-}}|$. However,
that must be larger than going from ${r^{+}}$ to ${s^{+}}$ on ${e^{+}}$ (i.e.,
$|{r^{+}}{s^{-}}|>|{r^{+}}{s^{+}}|$), reaching a contradiction.

Figure 24: Proof of Lemma 5.16. The zero shift implies that
$|{r^{+}}{s^{-}}|>|{r^{+}}{s^{+}}|$.

######  Lemma 5.18.

Let $F$ be a quadrilateral where two opposite edges are twin portal edges.
Then there exists a fragment $F^{\prime}$, equivalent to $F$, with $\Delta=0$.

######  Proof 5.19.

We proceed in the same way as in Lemma 5.4, except that now the direction of
the ray that we shoot depends also on the angle $\alpha$ between the portal
edges. Assume without loss of generality that ${e^{+}}$ is horizontal,
${e^{-}}$ is above ${e^{+}}$, and that it starts to the left of ${e^{+}}$. Let
$z$ be the slope of the line in the direction orthogonal to the portal start
points, and let $\alpha_{z}$ be the corresponding angle with the horizontal.
We begin at the leftmost vertex of ${e^{+}}$, and shoot a ray with angle slope
$\alpha_{z}-\alpha/2$. We consider the ray until it hits the boundary of $F$
for the first time. Every time the ray crosses the portal, we “cut” along this
ray, creating a new portal along it. This results in several smaller
fragments, which we then glue together again along the pieces of the original
portals, into a fragment $F^{\prime}$. See Figure 25 for an illustration. By
construction, $F^{\prime}$ has shift zero.

Figure 25: (left) A quadrilateral fragment with non-zero shift $\Delta$, and
(right) an equivalent fragment with zero shift.

We need one last lemma, analogous to Lemma 5.5, before we can prove the main
result in this section.

######  Lemma 5.20.

Consider a fragment $F$ with two portals ${e^{-}}$ and ${e^{+}}$. If there is
no point $p$ in $e$ such that the interior of the line segment
${p^{-}}{p^{+}}$ lies in the interior of $F$, then $F$ is $5$-happy.

######  Proof 5.21.

The proof is almost identical to that of Lemma 5.5.

Suppose that $F$ is not $5$-happy. Assume without loss of generality that
${e^{-}}$ is above ${e^{+}}$, and that ${e^{-}}$ starts to the left of
${e^{+}}$. Then there is a shortest path $\pi$ whose intersection with $F$
consists of at least six connected components, and thus $\pi$ crosses the
portal at least five times, in points $p_{1},\ldots,p_{5}$. Since $\pi$ is a
shortest path, these components cannot share vertices (otherwise we could
simply shorten the path). It follows that $\pi({p_{2}^{+}},{p_{3}^{-}})$ must
be a line segment (otherwise, if it would include a vertex from $F$, such a
vertex would be shared with $\pi({p_{1}^{+}},{p_{2}^{-}})$ or with
$\pi({p_{3}^{+}},{p_{4}^{-}})$). Analogously, $\pi({p_{3}^{+}},{p_{4}^{-}})$
must be a line segment. Thus ${p_{2}^{+}}{p_{3}^{-}}{p_{4}^{-}}{p_{3}^{+}}$ is
an empty quadrilateral. Hence the interior of segment ${p_{3}^{-}}{p_{3}^{+}}$
is contained in $F$.

In this case it will be useful to have the following corollary.

######  Corollary 5.22.

Let $\mathcal{P}$ be a portalgon with one fragment $F$ and exactly one portal,
such that the angular bisector between the portal edges is horizontal. If
$\mathcal{P}$ is not 5-happy, then there exists a vertical line segment
connecting the two portal edges whose interior is inside $F$.

######  Proof 5.23.

Assume without loss of generality that the portal edges are diverging, with
${e^{-}}$ above ${e^{+}}$, and ${e^{-}}$ starting to the left of ${e^{+}}$.
The proof of Lemma 5.20 guarantees the existence of an empty quadrilateral
${p_{2}^{+}}{p_{3}^{-}}{p_{4}^{-}}{p_{3}^{+}}$. We have that the four vertices
of the empty quadrilateral appear, from left to right, in the order
${p_{2}^{+}},{p_{3}^{-}},{p_{3}^{+}},{p_{4}^{-}}$. Moreover, the horizontal
angular bisector, combined with the fact that ${e^{-}}$ starts to the left of
${e^{+}}$, imply that ${p_{3}^{-}}$ is strictly to the left of ${p_{3}^{+}}$.
Therefore the interior of the vertical line segment that goes upward from
${p_{3}^{+}}$ is in the interior of the empty quadrilateral, and therefore it
is also inside $F$.

######  Lemma 5.24.

Let $\mathcal{P}$ be a portalgon with one fragment $F$ with $n$ vertices, and
one portal. There exists a $5$-happy portalgon $\mathcal{P}^{\prime}$
equivalent to $\mathcal{P}$ consisting of at most three fragments and total
complexity $O(n)$.

######  Proof 5.25.

Assume without loss of generality that ${e^{+}}$ is horizontal, ${e^{-}}$ is
above ${e^{+}}$, and that it starts to the left of ${e^{+}}$. As before, we
consider both portal edges oriented left-to-right.

We now argue that when no three vertices of $F$ are collinear, and $F$ is not
already $5$-happy, we can split $F$ into at most seven $4$-happy fragments of
total complexity $O(n)$. Finally, we show how to reduce the number of
fragments to three, while remaining $4$-happy, even without the general
position assumption.

By Lemma 5.20, if there is no line segment of the form ${p^{-}}{p^{+}}$ fully
contained in $F$, $F$ is already $5$-happy. Let $m_{\ell}$ (resp., $m_{r}$) be
the leftmost (resp., rightmost) such segment; $m_{\ell}$ contains a vertex
$\ell$ of $F$ and $m_{r}$ contains a vertex $r$ of $F$ (possibly, $\ell$ or
$m$ is an endpoint of ${e^{-}}$ or ${e^{+}}$). Let ${a^{-}}$ and ${a^{+}}$ be
the intersection points of $m_{\ell}$ with ${e^{-}}$ and ${e^{+}}$, and let
${b^{-}}$ and ${b^{+}}$ be the intersection points of $m_{r}$ with ${e^{-}}$
and ${e^{+}}$. We cut the quadrilateral $Z={a^{-}}{b^{-}}{a^{+}}{b^{+}}$ from
$F$, which splits $F$ into at most seven fragments (since, by general
position, $\overline{{a^{-}}{a^{+}}}$ and $\overline{{b^{-}}{b^{+}}}$ contain
at most two reflex vertices each). We now transform $Z$ into a $2$-happy
fragment using Lemma 5.18. Let $T$ and $B$ be the fragments containing the
starting points of ${e^{-}}$ and ${e^{+}}$, respectively. We argue that $T$ is
$4$-happy. The argument that $B$ is $4$-happy is symmetric. The same holds for
the fragments containing the endpoints of ${e^{-}}$ and ${e^{+}}$. Any other
fragments (if they exist) contain only one portal edge and are thus $2$-happy
by Observation 5.

Consider the maximal connected components of a shortest path $\pi=\pi(s,t)$
with $F$. By Observation 5.1.1 such a component either: (i) contains $s$, (ii)
contains $t$, or (iii) connects a point $p_{i}$ on ${e^{-}}$ to a point
$q_{i}$ on ${e^{+}}$. Again by Observation 5.1.1 each such component can
intersect $\overline{{a^{-}}{a^{+}}}$ at most once, so each such component can
intersect $T$ at most once.

We now further classify the type (iii) components into three types, depending
on whether $p_{i}$ lies on the part of ${e^{-}}$ in $T$ and whether $q_{i}$
lies on the part of ${e^{+}}$ in $B$.

If $p_{i}$ lies outside $T$, then Observation 5.1.1 implies that
$\pi(p_{i},q_{i})$ does not intersect (the interior of) $T$ at all since
$\pi(p_{i},q_{i})$ would have to intersect $\overline{a\ell}$ twice.

If $p_{i}$ lies in $T$ and $q_{i}$ lies in $B$, then Observation 5.1.1 implies
that $\pi(p_{i},q_{i})$ contains point $\ell$. Hence, there can be at most one
such component of this type that intersects $T$.

If $p_{i}$ lies in $T$ but $q_{i}$ lies outside of $B$, we have that
$q_{i}={t^{+}}$ for some point ${t^{-}}$ on $e$. If the component starting in
${t^{-}}$ is again of type (iii) (i.e., ${t^{-}}=p_{i+1}$) it cannot intersect
$B$ as this would imply that $\pi(p_{i+1},q_{i+1})$ intersects
$\pi(p_{i},q_{i})$. Nor can it intersect $T$ (since $q_{i+1}$ lies on
${e^{+}}$ it would have to intersect $\overline{a\ell}$ twice). The same
argument holds for any component on $\pi(p_{j},q_{j})$ with $j>i$. Hence,
$\pi(p_{i},q_{i})$ intersects $T$ only if this is the last component of type
(iii). Clearly, there is only one such a component.

It follows that there are only four components of $\pi\cap F$ that intersect
$T$, and each such component intersects $T$ in only one consecutive subpath.
Hence $T$ is $4$-happy.

We conclude that the portalgon $\mathcal{P}$’ that we obtain is $4$-happy,
equivalent to $\mathcal{P}$, and has at most seven fragments. Furthermore,
every vertex of $\mathcal{P}$ appears in at most $O(1)$ fragments of
$\mathcal{P}^{\prime}$, and thus $\mathcal{P}^{\prime}$ has complexity $O(n)$.

Finally, observe that (before splitting $F$) we can actually shift the left
and right sides of $Z$ inwards by some arbitrarily small $\varepsilon$ (in
particular, something smaller than the smallest distance between two non-
adjacent edges of $Z$). It then follows that $F$ is now split into only three
fragments, two of which are already $4$-happy. We transform the remaining
fragment (parallelogram $Z$) into a $2$-happy parallelogram as before. We now
obtain three fragments, of total complexity $O(n)$), even if $F$ contains
three or more collinear vertices.

####  5.2.2 Computation

In this section we focus on the case where $\mathcal{P}$ consists of just one
fragment with one portal.

######  Lemma 5.26.

Let $\mathcal{P}=(\mathcal{F},P)$ be an $h$-happy portalgon with $n$ vertices,
one fragment, and one portal. An equivalent $5$-happy portalgon
$\mathcal{P}^{\prime}$ with $3$ fragments and total complexity $O(n)$ can be
computed in $O(n+h)$ time.

######  Proof 5.27.

We follow the approach in Lemma 5.24, splitting the fragment into three parts;
left, middle, and right so that: (i) left and right have complexity $O(n)$,
but they are already 4-happy, and (ii) middle, with $O(1)$ complexity and
allows for $h$ portal crossings (since $\mathcal{P}$ is $h$-happy). It then
follows that the cost of tracing the ray through the left and right parts (by
repeatedly computing the first intersection point) is $O(n)$, and the cost of
tracing the ray through the middle part is $O(h)$.

What remains to explain is how to compute this partition.

We apply a constant number of rigid transformations to the fragment so that
the angular bisector between the two portal edges is horizontal, the portal
edges are diverging, and the top portal edge starts to the left of the bottom
one. Note that the required transformations preserve shortest paths.

It follows that the segment connecting the left endpoints has negative slope,
and thus the ray that we shoot has positive slope. Let $p_{i}$ be the
$i^{\mathrm{th}}$ point where the ray “enters” the fragment (i.e., at the
bottom edge), and let $q_{i}$ be the $i^{\mathrm{th}}$ point where it “exits”
the fragment (i.e., at the top edge).

We observe that $p_{i+1}$ lies right of $q_{i}$. Initially, this is due to the
ray having positive slope. Since the starting point of the top portal lies to
the left of the starting point of the bottom portal, each entry point is to
the right of the immediately previous exit point. After every portal crossing,
the slope of the ray decreases, approaching zero. As a consequence, the ray
only crosses any vertical line once.

By Corollary 5.22, we know that if the fragment is not already 5-happy, there
is a vertical line segment between the two portal edges that is fully
contained in it. Thus we can assume that is the case. Then we can cut the
fragment along two vertical segments; one through the rightmost point
“protruding into” the quadrilateral defined by the two portal edges from the
left, and one through the leftmost point protruding from the right.

We can compute these points by computing the hourglass defined by the two
portal edges (i.e., computing the shortest paths connecting the leftmost and
rightmost portal endpoints). This takes $O(n)$ time.

We can improve the previous running time by avoiding tracing the ray in the
middle fragment explicitly.

######  Lemma 5.28.

Let $\mathcal{P}=(\mathcal{F},P)$ be an $h$-happy portalgon with $n$ vertices,
one fragment, and one portal. An equivalent $5$-happy portalgon
$\mathcal{P}^{\prime}$ with $3$ fragments and total complexity $O(n)$ can be
computed in $O(n+\log h)$ time.

######  Proof 5.29.

Following Lemma 5.26, we split the portalgon into three parts in $O(n)$ time.
The middle piece is the only one that may not be happy yet, therefore we have
to apply to it the procedure in Lemma 5.18. This comes down to tracing the ray
through the middle piece. To this end, one can apply Lemma 7.1 of Erickson and
Nayyeri [11], presented in the context of annular ray shooting, to trace the
ray through the middle piece in $O(1+\log k)$ time, for $k$ the number of
intersections between the ray and the portal. For completeness, we describe
here an more direct procedure that yields the same result. Consider a shortest
path from $p$ to $q$ that goes through a portal $e$ several times. Given a
crossing point of the shortest path with portal edge ${e^{-}}$, the point on
${e^{+}}$ where the ray crosses ${e^{+}}$ next can be computed by a
composition of a translation and a rotation. Therefore it can be expressed as
a matrix multiplication. To compute the last point where the shortest path
crosses $e$, we need to figure out the power $k$ that corresponds to the last
time the ray fully crosses the fragment. We do know know $k$, but we can find
it in $O(\log k)$ by doing an exponential search. We also need to know the
total length of the ray, to actually construct the new fragment, but this we
can get by applying $M^{k}$ to the starting point, and simply measuring the
distance directly (we do not need to know the lengths of individual pieces).
The results now follows by observing that since $\mathcal{P}$ is $h$-happy, we
have $k=O(h)$.

An interesting open question is whether the dependency on $h$ is necessary at
all.

###  5.3 Generalization based on fragment graph analysis

Recall that we defined the _fragment graph_ $G$ of a portalgon $\mathcal{P}$
as the graph that has a node for every fragment, and two fragments are
connected by a link if there is a portal whose portal edges occur in these two
fragments; see Figure 4.555We use the terms node and link for the fragment
graph, to distinguish from the vertices and edges of the fragments themselves.

We now argue how to reduce a portalgon to a simpler portalgon for the purpose
of transforming it into a happy one; concretely, we show that if the fragment
graph of the original portalgon has at most one cycle, then it is sufficient
to consider the case of reconfiguring a single fragment with a single portal.

Since, by Observation 5 any fragment with only one portal edge is 2-happy, the
simplest non-trivial case occurs when each fragment in the portalgon has two
portal edges. Indeed, we may otherwise simply remove the leaves.

######  Lemma 5.30.

Let $\mathcal{P}$ be a portalgon and $G$ its fragment graph. Let $G^{\prime}$
be the graph we obtain by removing all leaves from $G$. The corresponding
portalgon $\mathcal{P}^{\prime}$ is happy if and only if $\mathcal{P}$ is
happy.

######  Proof 5.31.

Let $F$ be a fragment that is a leaf in $G$; $F$ is connected to the remainder
of $\mathcal{P}$ by some portal $e$. By Observation 5, $F$ is always happy.
Furthermore, since no shortest path crosses $e$ twice, any other fragment $X$
of $\mathcal{P}$ is happy if an only if in $\mathcal{P}$ with $F$ removed and
$e$ replaced by a boundary edge, $X$ is happy.

We now argue that we can always safely put leaves back after rearranging the
remaining portalgon.

######  Lemma 5.32.

Let $\mathcal{P}$ be an arbitrary portalgon with complexity $n$ and happiness
$h$, and let $F$ be an unrelated fragment with a single portal edge $e$, of
complexity $m$. Let $S$ be a collection of boundary edges of $\mathcal{P}$ of
total length $|e|$. Then the portalgon $\mathcal{P}^{\prime}$ we obtain by
turning the edges of $S$ into portal edges and linking them to pieces of $e$
has complexity $O(n+m)$ and happiness $h$.

######  Proof 5.33.

To argue about the complexity, note that the number of edges in $S$ is at most
$O(n)$, and we cut the portal edge $e$ into $|S|$ pieces, so clearly the
resulting complexity is $O(n+m)$.