11institutetext: Ben Gurion University of the Negev, Beer Sheva, Israel
11email<EMAIL_ADDRESS>
22institutetext: Stony Brook University, Stony Brook, NY, USA 22email:
<EMAIL_ADDRESS>
33institutetext: Track160 33email<EMAIL_ADDRESS>
# Minimum-link $C$-Oriented Paths Visiting a Sequence of Regions in the Plane

Kerem Geva 11 Matthew J. Katz 11 Joseph S. B. Mitchell 22 Eli Packer 33

###### Abstract

Let $E=\\{e_{1},\ldots,e_{n}\\}$ be a set of $C$-oriented disjoint segments in
the plane, where $C$ is a given finite set of orientations that spans the
plane, and let $s$ and $t$ be two points. We seek a minimum-link $C$-oriented
tour of $E$, that is, a polygonal path $\pi$ from $s$ to $t$ that visits the
segments of $E$ in order, such that, the orientations of its edges are in $C$
and their number is minimum. We present an algorithm for computing such a tour
in $O(|C|^{2}\cdot n^{2})$ time. This problem already captures most of the
difficulties occurring in the study of the more general problem, in which $E$
is a set of not-necessarily-disjoint $C$-oriented polygons.

##  1 Introduction

We consider the problem in which we are given a sequence of regions, ${\cal
R}=(R_{1},R_{2},\ldots,R_{n})$, where each $R_{i}$ is a subset of an
underlying geometric domain, and our goal is to compute a tour (a path or a
cycle) within the domain that visits the regions $\cal R$ in the given order
and is optimal in some prescribed sense. Optimality might be based on the
Euclidean length of the tour, the number of turns in a polygonal tour (or,
equivalently, the number of links (edges) in the tour), a weighted cost
function, etc. There are also variants of the problem in which it is important
to specify exactly what constraints there are on the ordered visitation of the
regions, particularly if the regions are not disjoint. The problem arises
naturally and is also motivated by applications in curve simplification (e.g.,
[5]), vehicle routing (e.g., the traveling salesperson problem (TSP); see
[7]), search and exploration (e.g., [3]), computing structures on imprecise
points [6], task sequencing in robotics (see [2, 1]), etc.

In this paper we focus on the version of the problem in which the regions
$R_{i}$ are disjoint $C$-oriented line segments (with orientations/slopes from
a finite set $C$) in the plane, the tour is required to be polygonal and
$C$-oriented, and the optimality criterion is to minimize the number of links
(equivalently, the number of turns, or vertices in the polygonal tour). We
briefly mention generalizations (deferred to the full paper), including the
case in which the regions $R_{i}$ are more general than disjoint line
segments.

More formally, let $C$ be a finite set of orientations, which can be thought
of as points on a unit circle centered at the origin. We assume that (i) $C$
spans the plane, i.e., for any two points $p,q$ in the plane, there exists a
two-link (directed) path from $p$ to $q$ (or a one-link path), such that the
orientation of the edges in the path belong to $C$, and (ii) for any
orientation $c_{i}\in C$, the orientation $\overline{c_{i}}$ is also in $C$,
where $\overline{c_{i}}$ is the opposite orientation of $c_{i}$. The
requirement for paths to be $C$-oriented arises in some settings (mechanical
constraints) but also has advantages in lower/upper bounding of the turn
angles, in comparison with polygonal paths having general links, which may
form arbitrarily sharp turns.

We focus on the following problem: _Minimum-link $C$-oriented tour of a
sequence of $C$-oriented segments_: Let $E=\\{e_{1},\ldots,e_{n}\\}$ be a set
of $C$-oriented disjoint segments, that is, if we think of $e\in E$ as a
directed segment, by arbitrarily picking one of the two possible directions,
then $e$’s orientation belongs to $C$. Let $s$ and $t$ be two points that do
not belong to any of the segments in $E$. A _tour_ of $E$ is a polygonal path
$\pi$ that begins at $s$ and ends at $t$ with the following property: There
exists a sequence of points $p_{1},\ldots,p_{n}$ on $\pi$, such that, $p_{i}$
precedes $p_{i+1}$, for $1\leq i\leq n-1$, and $p_{i}\in e_{i}$, for $1\leq
i\leq n$. A tour is $C$-oriented, if the orientation of each of its edges
belongs to $C$. We wish to compute a $C$-oriented minimum-link tour of $E$,
that is, a $C$-oriented tour consisting of a minimum number of links (i.e.,
edges).

Our main contribution is an efficient algorithm to compute a minimum-link
$C$-oriented tour of a sequence of $n$ disjoint $C$-oriented line segments, in
time $O(|C|^{2}\cdot n^{2})$. (The algorithm becomes $O(n)$ in the special
case of $|C|=4$, e.g., axis-oriented paths.)

### Related Work

In the _touring polygons problem_ (TPP), one seeks a tour that is shortest in
Euclidean length that visits a sequence of polygons; such a tour is found in
polynomial time if the polygons are convex and is NP-hard in general (and has
an FPTAS) [3]. Minimization of the link length of a tour visiting a sequence
of (possibly overlapping) disks is studied in [5], where the motivation for
this “ordered stabbing” problem was curve and map simplification (see also
[9]). In contrast with our problem specification, in [5] the path edges are
allowed to be of arbitrary orientation, not required to be $C$-oriented. This
assumption leads to particular efficiency, as one can use an extension of
linear-time line stabbing methods (see Egyed and Wenger [4]) to execute a
greedy algorithm efficiently. Computing a minimum-link $C$-oriented path from
start to goal among obstacles has been studied as well, without requiring
visitation of a sequence of regions; see [8, 10].

##  2 Preliminaries

Notation. For any $1\leq i\leq n$, let $l(e_{i})$ be the number of links in a
minimum-link path that begins at $s$ and ends at a point on $e_{i}$. We only
consider $C$-oriented paths to $e_{i}$ that visit the segments
$e_{1},\ldots,e_{i}$, as defined above. We refer to the number of links in
such a path as its _length_. We distinguish between paths to $e_{i}$ both by
their length and by the orientation of their last link. Let $I(e_{i},c_{j})$
($I^{+}(e_{i},c_{j})$) be the set of maximal intervals on $e_{i}$ formed by
all paths of length $l(e_{i})$ ($l(e_{i})+1$) from $s$ to $e_{i}$, whose last
link has orientation $c_{j}$. We set $I(e_{i})=\bigcup_{c\in C}I(e_{i},c)$ and
$I^{+}(e_{i})=\bigcup_{c\in C}I^{+}(e_{i},c)$.

For an orientation $c_{j}\in C$, let $c_{j+1}$ and $c_{j-1}$ be the
orientations in $C$ that immediately succeed $c_{j}$ and precede $c_{j}$ in
clockwise order, respectively. We denote by $\phi(c_{j},c_{k})$ the set of
orientations in $C$ between $c_{j}$ and $c_{k}$ (in clockwise order from
$c_{j}$), not including $c_{j}$ and $c_{k}$. Finally, we denote the ray
emanating from $p$ in orientation $c_{j}$ by $Ray(p,c_{j})$ and the line
through $p$ parallel to a segment of orientation $c_{j}$ by $Line(p,c_{j})$.

Let $a$ be an interval on $e_{i}$ that belongs to one of the sets $I(e_{i})$
or $I^{+}(e_{i})$. Then $a$ has a length $l_{a}$ (which is either $l(e_{i})$
or $l(e_{i})+1$) and an orientation $c_{a}\in C$ associated with it. We denote
the endpoints of $a$ by $a_{1}$ and $a_{2}$, where $a_{1}$ is to the left of
$a_{2}$, when approaching $a$ through a path corresponding to $a$ (i.e., a
path starting at $s$ and ending at a point in $a$, which is of length $l_{a}$
and whose last link is of orientation $c_{a}$). Next, we use $a$ to define two
regions of the plane, namely, $PT(a)$ and $\psi(a,c_{j})$.

Let $PT(a)$ denote the semi-slab consisting of all points that can be reached
by extending the last link of a path corresponding to $a$. We refer to such a
path as a path that _passes through $a$_ and continues in the same orientation
at which it reached $a$ (i.e., $c_{a}$). Thus, the region $PT(a)$ is the semi-
slab bounded by the rays $Ray(a_{1},c_{a}),Ray(a_{2},c_{a})$ and the interval
$a$ (see, e.g., the red region in Figure 2). Similarly, let $\psi(a,c_{j})$ be
the region of all points that can be reached by a path that passes through $a$
and then, not necessarily immediately, turns and continues in orientation
$c_{j}$. Thus, $\psi(a,c_{j})=\bigcup_{q\in PT(a)}Ray(q,c_{j})$, for example
if $c_{j}=\overline{c_{a}}$, then $\psi(a,c_{j})$ is the slab defined by the
lines $Line(a_{1},c_{a})$ and $Line(a_{2},c_{a})$ (for additional examples see
Figure 8).

Finally, for an interval $b\in I^{+}(e_{i})$, we set $\delta(b)=\\{a\in
I(e_{i})|a\subseteq b\\}$.

We now show that the sets $I(e_{i})$ and $I^{+}(e_{i})$ are sufficient, in the
sense that there exists a minimum-link tour of $E$ whose portion from $s$ to
$e_{i}$ corresponds to an interval in $I(e_{i})\cup I^{+}(e_{i})$. Assume this
is false, and let $\pi$ be a minimum-link tour of $E$, such that its portion
$\pi_{i}$ from $s$ to $e_{i}$ does not correspond to an interval in
$I(e_{i})\cup I^{+}(e_{i})$. Then, the length of $\pi_{i}$ (denoted
$|\pi_{i}|$) is at least $l(e_{i})+2$. Let $p$ be the point on $e_{i}$ where
$\pi_{i}$ ends, and denote the portion of $\pi$ from $p$ to $t$ by $\pi^{i}$.
Then $|\pi|\geq l(e_{i})+2+|\pi^{i}|$, if $\pi$ makes a turn at $p$, or
$|\pi|=l(e_{i})+2+|\pi^{i}|-1$, otherwise. Consider any path
$\pi^{\prime}_{i}$ from $s$ to $e_{i}$ that corresponds to an interval in
$I(e_{i})$ and let $p^{\prime}$ be the point on $e_{i}$ where
$\pi^{\prime}_{i}$ ends. Then, the tour obtained by $\pi^{\prime}_{i}$, the
edge $p^{\prime}p$ and $\pi^{i}$ is a tour of $E$ of length at most
$l(e_{i})+1+|\pi^{i}|\leq|\pi|$. We have thus shown that

###### Claim 1

There exists a minimum-link tour of $E$ whose portion from $s$ to $e_{i}$
corresponds to an interval in $I(e_{i})\cup I^{+}(e_{i})$, for $1\leq i\leq
n$.

Finally, since our assumptions on the set of orientations $C$ imply that there
exists a two-link path from $p$ to $q$, for any pair of points $p,q$ in the
plane, we have

###### Claim 2

$l(e_{i-1})\leq l(e_{i})\leq l(e_{i-1})+2$, for $1\leq i\leq n$ (where
$l(e_{0})=0$).

##  3 The Main Algorithm

In this section, we present an algorithm for computing a minimum-link tour of
$E$. The algorithm consists of two stages. In the first stage, it considers
the segments of $E$, one at a time, beginning with $e_{1}$, and, at the
current segment $e_{i}$, it computes the sets $I(e_{i})$ and $I^{+}(e_{i})$
from the sets $I(e_{i-1})$ and $I^{+}(e_{i-1})$, associated with the previous
segment. In the second stage, it constructs a minimum-link tour of $E$,
beginning from its last link, by consulting the sets $I(\cdot)$ and
$I^{+}(\cdot)$ computed in the first stage.

We begin with several definitions that will assist us in the description of
the algorithm. Given a set $I$ of intervals on $e_{i}$, where each interval
$a\in I$ is associated with some fixed length (link distance) $l_{a}=l$ and an
orientation $c_{a}$, and $c_{j}\in C$, we define the sets of intervals
_+0-intervals, +1-intervals, +2-intervals_ on $e_{i+1}$ with respect to $I$
and $c_{j}$ (the definition of the first set does not depend on $c_{j}$).

The +0-intervals on $e_{i+1}$ consist of the intervals on $e_{i+1}$ formed by
passing through the intervals of $I$, without making any turns. It is
constructed by computing the interval $b=PT(a)\cap e_{i+1}$, for each $a\in
I$, and including it in the set, setting $l_{b}=l$ and $c_{b}=c_{a}$, if it is
not empty.

The +1-intervals on $e_{i+1}$ associated with orientation $c_{j}$ consist of
the intervals on $e_{i+1}$ formed by passing through the intervals of $I$ and
then making a turn in orientation $c_{j}$. It is constructed by computing the
interval $b=\psi(a,c_{j})\cap e_{i+1}$, for each $a\in I$, and including it in
the set, setting $l_{b}=l+1$ and $c_{b}=c_{j}$.

The +2-intervals on $e_{i+1}$ associated with orientation $c_{j}$ consist of
the intervals on $e_{i+1}$ formed by passing through the intervals of $I$ and
then making two turns, where the first is in any orientation
$c\neq\overline{c_{a}}$ and the second is in orientation $c_{j}$; see Lemma 3.

We construct it as follows. First, we check if there is an interval $a\in I$
such that $c_{a}\notin\\{c_{j-1},c_{j},c_{j+1}\\}$. If there is such an
interval, we include the interval $b=e_{i+1}$, setting $l_{b}=l+2$ and
$c_{b}=c_{j}$, and stop; see Lemma 4. Otherwise, for each $a\in I$, we include
the intervals $b^{+}=\psi(a,\overline{c_{a}}_{+1})\cap e_{i+1}$ and
$b^{-}=\psi(a,\overline{c_{a}}_{-1})\cap e_{i+1}$, provided that they are not
empty, and set $l_{b^{+}}=l_{b^{-}}=l+2$ and $c_{b^{+}}=c_{b^{-}}=c_{j}$; see
paragraph following Lemma 4.

###  3.1 Stage I

We are now ready to describe the first stage of the algorithm. It is
convenient to treat the points $s$ and $t$ as segments $e_{0}$ and $e_{n+1}$,
respectively. We set $l(e_{0})=0$ and, for each $c_{j}\in C$, we insert the
interval $a=e_{0}$, after setting $l_{a}=0$ and $c_{a}=c_{j}$, into
$I(e_{0},c_{j})$. Similarly, for each $c_{j}\in C$, we insert the interval
$a=e_{0}$, after setting $l_{a}=1$ and $c_{a}=c_{j}$, into
$I^{+}(e_{0},c_{j})$.

We iterate over the segments $e_{1},\ldots,e_{n+1}$, where in the $i$’th
iteration, $1\leq i\leq n+1$, we compute $l(e_{i})$ and the pair of sets
$I(e_{i})$ and $I^{+}(e_{i})$. Assume we have already processed the segments
$e_{0},\ldots,e_{i}$, for some $0\leq i\leq n$. We describe the next
iteration, in which we compute $l(e_{i+1})$ and the sets $I(e_{i+1})$ and
$I^{+}(e_{i+1})$.

For each $c_{j}\in C$, we compute the +0-intervals on $e_{i+1}$ with respect
to $I(e_{i},c_{j})$ and store them in $I(e_{i+1},c_{j})$. If at least one of
the sets $I(e_{i+1},c_{j})$ is non-empty, we set $l(e_{i+1})=l(e_{i})$
(otherwise $l(e_{i+1})>l(e_{i})$). Next, for each $c_{j}\in C$, we compute the
+0-intervals on $e_{i+1}$ with respect to $I^{+}(e_{i},c_{j})$ and the
+1-intervals on $e_{i+1}$ with respect to $I(e_{i})\setminus I(e_{i},c_{j})$
(and $c_{j}$). We store these intervals (if exist) either in
$I^{+}(e_{i+1},c_{j})$, if $l(e_{i+1})=l(e_{i})$, or in $I(e_{i+1},c_{j})$, if
$l(e_{i+1})>l(e_{i})$. If we performed the latter option, then we set
$l(e_{i+1})=l(e_{i})+1$. Finally, if we performed one of the two options, then
we repeatedly merge overlapping intervals in the set (either
$I^{+}(e_{i+1},c_{j})$ or $I(e_{i+1},c_{j})$), until there are no such
intervals.

If $l(e_{i+1})>l(e_{i})$, then, for each $c_{j}\in C$, we compute the
+2-intervals on $e_{i+1}$ with respect to $I(e_{i})$ and the +1-intervals on
$e_{i+1}$ with respect $I^{+}(e_{i})\setminus I^{+}(e_{i},c_{j})$. We store
these intervals (if exist) either in $I^{+}(e_{i+1},c_{j})$, if
$l(e_{i+1})=l(e_{i})+1$, or in $I(e_{i+1},c_{j})$, otherwise (i.e., we still
have not fixed $l(e_{i+1})$). If we performed the latter option, then we set
$l(e_{i+1})=l(e_{i})+2$, and, as above, if we performed one of the two
options, then we repeatedly merge overlapping intervals in the set, until
there are no such intervals.

Finally, if $l(e_{i+1})=l(e_{i})+2$, then, for each $c_{j}\in C$, we set
$I^{+}(e_{i+1},c_{j})=e_{i+1}$; see Claim 5.

###  3.2 Stage II

In this stage we use the information collected in the first stage to construct
a minimum-link tour $\pi$ of $E$.

We construct $\pi$ incrementally beginning at $t$ and ending at $s$. That is,
in the first iteration we add the portion of $\pi$ from $t$ to $e_{n}$, in the
second iteration we add the portion from $e_{n}$ to $e_{n-1}$, etc. Assume
that we have already constructed the portion of $\pi$ from $t$ to $e_{i}$,
where this portion ends at point $p$ of interval $a$ on $e_{i}$. We describe
in Algorithm 1 (see Appendix 0.A.1) how to compute the portion from $e_{i}$ to
$e_{i-1}$, which begins at the point $p$ of interval $a$ and ends at a point
$p^{\prime}$ of interval $b$ on $e_{i-1}$ (where $b\in I(e_{i-1})\cup
I^{+}(e_{i-1})$) and consists of $l_{a}-l_{b}+1$ links. Before continuing to
the next iteration, we set $p=p^{\prime}$ and $a=b$.

After adding the last portion, which ends at $s$, we remove all the redundant
vertices from $\pi$, i.e., vertices at which $\pi$ does not make a turn.

##  4 Analysis

In this section, we prove the correctness of our two-stage algorithm and bound
its running time, via a sequence of lemmas and claims.

###### Lemma 1

For any interval $a\in I(e_{i})$ and for any $c_{j}\in C\setminus\\{c_{a}\\}$,
there exists an interval $b\in I^{+}(e_{i},c_{j})$ such that $a\subseteq b$,
for $1\leq i\leq n$.

###### Proof

Let $p\in a$, then there is a path $\pi_{i}$ of length $l(e_{i})$ that begins
at $s$, ends at $p$, and whose last link is of orientation $c_{a}$. By making
a turn at $p$ in orientation $c_{j}$ (without extending $\pi_{i}$), we obtain
a path $\pi^{\prime}_{i}$ of length $l(e_{i})+1$, whose last link is of
orientation $c_{j}$. Therefore, there is an interval $b\in I^{+}(e_{i},c_{j})$
such that $p\in b$, and since (by construction) there are no overlapping
intervals in $I^{+}(e_{i},c_{j})$, we conclude that $a\subseteq b$.

###### Lemma 2

For any $1\leq i\leq n-1$ and $c_{j}\in C$, if there is an interval $a\in
I(e_{i},\overline{c_{j}})\cup I^{+}(e_{i},\overline{c_{j}})$ such that
$PT(a)\cap e_{i+1}\neq\emptyset$, then, for any interval $b\in
I(e_{i},c_{j})\cup I^{+}(e_{i},c_{j})$, we have that $PT(b)\cap
e_{i+1}=\emptyset$.

###### Proof

If there exist intervals $a\in I(e_{i},\overline{c_{j}})\cup
I^{+}(e_{i},\overline{c_{j}})$ and $b\in I(e_{i},c_{j})\cup
I^{+}(e_{i},c_{j})$, such that $e_{i+1}$ intersects both $PT(a)$ and $PT(b)$,
then $e_{i+1}$ must intersect $e_{i}$ (see Figure 2) — contradiction.

The following claim bounds the number of intervals with associated length and
orientation $l(e_{i})+1$ and $c_{j}$, respectively, that are ‘created’ on
$e_{i+1}$.

###### Claim 3

At most
$\max\left\\{|I(e_{i},\overline{c_{j}})|,|I^{+}(e_{i},c_{j})|\right\\}+2$
intervals with associated length and orientation $l(e_{i})+1$ and $c_{j}$,
respectively, are ‘created’ on $e_{i+1}$, during the execution of the
algorithm.

###### Proof

There are two ways to reach a point on $e_{i+1}$ with a path of length
$l(e_{i})+1$ whose last link is of orientation $c_{j}$. The first is by
passing through one of the intervals in $I(e_{i})\setminus I(e_{i},c_{j})$ and
then making a turn in orientation $c_{j}$. The second is by passing through
one of the intervals in $I^{+}(e_{i},c_{j})$, without making any turn. That
is, the intervals on $e_{i+1}$ with associated length $l(e_{i})+1$ and
associated orientation $c_{j}$ are determined by the intervals in
$I^{+}(e_{i},c_{j})\cup(I(e_{i})\setminus I(e_{i},c_{j}))$.

Consider an interval $b\in I^{+}(e_{i},c_{j})$ (e.g., the blue interval in
Figure 2), and let $c\in C$ be the orientation of $e_{i}$ when directed from
$b_{1}$ to $b_{2}$. We divide $\delta(b)\setminus I(e_{i},\overline{c_{j}})$
into four subsets as follows: $A=\\{a\in\delta(b)\mid
c_{a}\in\phi(c_{j},c)\cup\\{c\\}\\}$, $B=\\{a\in\delta(b)\mid
c_{a}\in\phi(c,\overline{c_{j}})\\}$, $C=\\{a\in\delta(b)\mid
c_{a}\in\phi(\overline{c_{j}},\overline{c})\\}$, and $D=\\{a\in\delta(b)\mid
c_{a}\in\phi(\overline{c},c_{j})\cup\\{\overline{c}\\}\\}$. We denote by
$R_{b\cup A}$ the region of all points that can be reached by a path that
passes through $b$, or passes through $a\in A$ and then makes a turn in
orientation $c_{j}$ (i.e., $R_{b\cup A}=PT(b)\cup\bigcup_{a\in
A}\psi(a,c_{j})$). We compute the boundary of $R_{b\cup A}$ from $PT(b)$, by
adding the regions $\psi(a,c_{j})$, one at a time, for each interval $a\in A$.

Let $\psi(a,c_{j})$, for some $a\in A$, be the region that is added in the
first step (see the red interval in Figure 2). Since
$(a_{1},a_{2})\subseteq(b_{1},b_{2})$ and $c_{a}\in\phi(c_{j},c)\cup\\{c\\}$,
$Ray(a_{2},c_{a})$ and $Ray(b_{2},c_{j})$ intersect at a point $p_{a}$ (see
Figure 2). By passing through $a$ and then turning before reaching
$Ray(b_{2},c_{j})$ (i.e., at one of the points belonging to $PT(a)\cap
PT(b)$), we cannot reach any point that is not already in $PT(b)$. However, by
turning after crossing $Ray(b_{2},c_{j})$, we can reach points that are in the
area bounded by $Ray(p_{a},c_{j})$ and $Ray(p_{a},c_{a})$ (the shaded area in
Figure 2). Thus, the region $R_{b\cup A}$ at the end of the first step, is
bounded by $Ray(b_{1},c_{j})$, $(b_{1},b_{2})$, $(b_{2},p_{a})$ and
$Ray(p_{a},c_{a})$, as can be seen in Figure 2.

Figure 1:  If $e_{i+1}$ intersects both $PT(a)$ (red) and $PT(b)$ (blue), then
$e_{i+1}$ must intersect $e_{i}$.

Figure 2: The region $R_{b\cup A}$ at the end of the first step.

Notice the semi-infinite convex 2-chain that we obtain at the end of the first
step, namely, the chain consisting of $(b_{2},p_{a})$ followed by
$Ray(p_{a},c_{a})$. It is easy to see that the region $R_{b\cup A}$ at the end
of the last step, is bounded by $Ray(b_{1},c_{j})$, $(b_{1},b_{2})$, and a
semi-infinite convex chain, denoted $l_{A}$, consisting of at most $|A|+1$
edges (see red chain in Figure 3(c)). Finally, if $A=\emptyset$, then
$R_{b\cup A}=PT(b)$ and we set $l_{A}=Ray(b_{2},c_{j})$.

Next, we set $R_{b\cup D}=PT(b)\cup\bigcup_{a\in D}\psi(a,c_{j})$, and compute
the convex chain $l_{D}$, which, together with $Ray(b_{2},c_{j})$ and
$(b_{1},b_{2})$, defines the boundary of $R_{b\cup D}$. Once again, if
$D=\emptyset$, we set $l_{D}=ray(b_{1},c_{j})$.

Finally, we compute in a similar manner the convex chains $l_{B}$, which
defines (together with $Ray(b_{1},c_{j})$) the boundary of $R_{b\cup
B}=PT(b)\cup\bigcup_{a\in B}\psi(a,c_{j})$ (see purple chain in Figure 3(b)),
and $l_{C}$, which defines (together with $Ray(b_{2},c_{j})$) the boundary of
$R_{b\cup C}=PT(b)\cup\bigcup_{a\in C}\psi(a,c_{j})$.

We now set $R=R_{b\cup A}\cup R_{b\cup B}\cup R_{b\cup C}\cup R_{b\cup D}$,
then $R$ is the region of all points that can be reached by a path that passes
through $b$, or passes through $a\in\delta(b)\setminus
I(e_{i},\overline{c_{j}})$ and then makes a turn in orientation $c_{j}$.
Therefore, $R\cap e_{i+1}$ gives us the intervals on $e_{i+1}$ with length
$l(e_{i})+1$ and orientation $c_{j}$, which are created by passing through an
interval in $\\{b\\}\cup\delta(b)\setminus I(e_{i},\overline{c_{j}})$.

In order to find these intervals, we identify the boundary of $R$ in each of
the following four cases:

  * •

Case A: $B=\emptyset$ and $C=\emptyset$ (as illustrated in Figure 3(a))
In this case, $R=R_{b\cup A}\cup R_{b\cup D}$, since $R_{b\cup B}=R_{b\cup
C}=PT(b)$ and $PT(b)\subseteq R_{b\cup A},R_{b\cup D}$, and $R$’s boundary is
composed of $l_{A}$, $l_{D}$ and $b$.

  * •

Case B: $B\neq\emptyset$ and $C=\emptyset$ (as illustrated in Figure 3(b))
In this case, the boundary of $R$ is composed of $l_{B}$ and $l_{D}$, since
$R_{b\cup A}\subseteq R_{b\cup B}$.

  * •

Case C: $B=\emptyset$ and $C\neq\emptyset$ (as illustrated in Figure 3(c))
In this case, the boundary of $R$ is composed of $l_{A}$ and $l_{C}$, since
$R_{b\cup D}\subseteq R_{b\cup C}$.

  * •

Case D: $B\neq\emptyset$ and $C\neq\emptyset$ (as illustrated in Figure 3(d))
in this case, $R=R_{b\cup B}\cup R_{b\cup C}$, and its boundary is the convex
chain $l$ that is obtained from the chains $l_{B}$ and $l_{C}$, see Figure
3(d).

(a) Case A: If $B=\emptyset$ and $C=\emptyset$, then $R$ is bounded by $l_{A}$
(red), $l_{D}$ (green) and $b$.

(b) Case B: If $B\neq\emptyset$ and $C=\emptyset$, then $R$ is bounded by
$l_{B}$ (purple) and $l_{D}$ (green).

(c) Case C: If $B=\emptyset$ and $C\neq\emptyset$, then $R$ is bounded by
$l_{A}$ (red) and $l_{C}$ (dark blue).

(d) Case D: If $B\neq\emptyset$ and $C\neq\emptyset$, then $R$ is bounded by
the chain $l$ obtained from $l_{B}$ (purple) and $l_{C}$ (dark blue).

Figure 3: The boundary of $R$.

We now examine how $e_{i+1}$ can intersect $R$, in each of these cases. First,
if $e_{i+1}$ does not intersect the boundary of $R$, then either $R\cap
e_{i+1}=e_{i+1}$ or $R\cap e_{i+1}=\emptyset$. In the former case, one
interval is formed on $e_{i+1}$, which contains both its endpoints, and in the
latter case, no interval is formed on $e_{i+1}$. Next, assume that $e_{i+1}$
intersects the boundary of $R$. We distinguish between the case where there is
an interval $h\in I(e_{i},\overline{c_{j}}$) such that $PT(h)\cap
e_{i+1}\neq\emptyset$, and the case where there is no such interval.

There is an interval $h\in I(e_{i},\overline{c_{j}}$) such that $PT(h)\cap
e_{i+1}\neq\emptyset$.
Then, by Lemma 2, $PT(b)\cap e_{i+1}=\emptyset$.

If Case A: Clearly, $e_{i+1}$ cannot intersect both $l_{A}$ and $l_{D}$, since
this would imply $PT(b)\cap e_{i+1}\neq\emptyset$ (see Figure 5(a)).
Therefore, $e_{i+1}$ intersects exactly one of these chains, either at a
single point or at two points. If $e_{i+1}$ intersects the chain at a single
point $q$, then a single interval is formed on $e_{i+1}$, whose endpoints are
$q$ and the endpoint of $e_{i+1}$ that lies in $R$ (see the edge $e^{1}_{i+1}$
in Figure 4(a)). If $e_{i+1}$ intersects the chain at two points, $p$ and
$p^{\prime}$, then two intervals are formed on $e_{i+1}$. The endpoints of
these intervals are $p$ and $p^{\prime}$ on one side and the corresponding
endpoints of $e_{i+1}$ on the other side (see the edge $e^{2}_{i+1}$ in Figure
4(a)).

If Case B: Unlike Case A, the fact that $PT(b)\cap e_{i+1}=\emptyset$ does not
prevent $e_{i+1}$ from intersecting both $l_{B}$ and $l_{D}$. However,
$e_{i+1}$ can intersect these chains in at most two points (in total), and as
in Case A at most two intervals are formed on $e_{i+1}$, where each of them
contains an endpoint of $e_{i+1}$ (see Figure 5(b)).

If Case C: Since Cases B and C are symmetric, at most two intervals are formed
on $e_{i+1}$, each of which contains an endpoint of $e_{i+1}$.

If Case D: If $e_{i+1}$ intersects $l$ at a single point $q$, then a single
interval is formed on $e_{i+1}$, whose endpoints are $q$ and the endpoint of
$e_{i+1}$ that lies in $R$. If $e_{i+1}$ intersects $l$ at two points $p$ and
$p^{\prime}$, then $R\cap e_{i+1}$ consist of all the points on $e_{i+1}$,
except for those in the interior of $(p,p^{\prime})$. Therefore, two intervals
are formed on $e_{i+1}$, and their endpoints are $p$ and $p^{\prime}$ on one
side and the corresponding endpoints of $e_{i+1}$ on the other side (see
Figure 4(b))

(a) Case A.

(b) Case D.

Figure 4: $e_{i+1}$ intersects $R$’s boundary either at a single point $q$ or
at two points $p$ and $p^{\prime}$.

We have shown that by passing through an interval in
$\\{b\\}\cup\delta(b)\setminus I(e_{i},\overline{c_{j}})$, at most two
intervals (with associated length $l(e_{i})+1$ and orientation $c_{j}$) are
formed on $e_{i+1}$. Moreover, each of these intervals contains an endpoint of
$e_{i+1}$. Therefore, the total number of such intervals that are formed on
$e_{i+1}$, by passing through an interval in $\bigcup_{b\in
I^{+}(e_{i},c_{j})}\\{b\\}\cup\delta(b)\setminus I(e_{i},\overline{c_{j}})$ is
at most two. (For each endpoint $p$ of $e_{i+1}$, we retain only the longest
interval with $p$ as one of its endpoints.)

Finally, observe that by passing through an interval in
$I(e_{i},\overline{c_{j}})$ and turning backwards in orientation $c_{j}$, at
most one interval is formed on $e_{i+1}$, which does not necessarily contain
an endpoint of $e_{i+1}$.

We conclude that at most $|I(e_{i},\overline{c_{j}})|+2$ intervals (with
associated length $l(e_{i})+1$ and orientation $c_{j}$) are formed on
$e_{i+1}$ during the execution of the algorithm (in the case that there is an
interval $h\in I(e_{i},\overline{c_{j}}$) such that $PT(h)\cap
e_{i+1}\neq\emptyset$). We have used the equality $\bigcup_{b\in
I^{+}(e_{i},c_{j})}\\{b\\}\cup\delta(b)=I^{+}(e_{i},c_{j})\cup
I(e_{i})\setminus I(e_{i},c_{j})$, which follows from Lemma 1.

We now proceed to the complementary case.

For any interval $h\in I(e_{i},\overline{c_{j}}$), $PT(h)\cap
e_{i+1}=\emptyset$. We defer the details of this case (which are similar to
those of the previous case) to Appendix 0.A.2. These details lead to the
conclusion that at most $|I^{+}(e_{i},c_{j})|+2$ intervals (with associated
length $l(e_{i})+1$ and orientation $c_{j}$) are formed on $e_{i+1}$ during
the execution of the algorithm in this case.

(a) $e_{i+1}$ intersects $R$’s boundary at two points $p_{A}$ and $p_{D}$,
creating a single internal interval (green) on $e_{i+1}$.

(b) $e_{i+1}$ intersects $R$’s boundary at two points $p_{B}$ and $p_{D}$,
creating two intervals (green), where each of them contains an endpoint of
$e_{i+1}$.

Figure 5: Cases A and B, where there is no such interval $h$.

Since only one of the two cases holds (i.e., either there is such an interval
$h$ or there is not), we conclude that at most
$max\left\\{|I(e_{i},\overline{c_{j}})|+2,|I^{+}(e_{i},c_{j})|+2\right\\}$
$=max\left\\{|I(e_{i},\overline{c_{j}})|,|I^{+}(e_{i},c_{j})|\right\\}+2$
intervals with associated length $l(e_{i})+1$ and orientation $c_{j}$ are
formed on $e_{i+1}$ during the execution of the algorithm. This completes the
proof of Claim 3.

###### Lemma 3

For any interval $a\in I(e_{i})$ and orientation $c_{j}\in C$, we do not need
to compute the interval on $e_{i+1}$ with associated length and orientation
$l(e_{i})+2$ and $c_{j}$, respectively, which is formed by passing through $a$
and then making two turns, where the first is in orientation
$\overline{c_{a}}$.

###### Proof

By Claim 2, $l(e_{i})\leq l(e_{i+1})\leq l(e_{i})+2$. So, the intervals on
$e_{i+1}$ of length $l(e_{i})+2$ are only relevant if $l(e_{i+1})>l(e_{i})$
(Claim 1). Assume therefore that $l(e_{i+1})>l(e_{i})$, and let $a\in
I(e_{i})$ (e.g., the red interval in Figure 6). Let $\pi$ be a tour of $E$
that passes through $a$ at a point $p_{i}$, makes a turn in orientation
$\overline{c_{a}}$ at point $p$, and makes another turn in orientation $c_{j}$
at point $p^{\prime}$, such that $\pi_{i+1}$ (the portion of $\pi$ from $s$ to
$e_{i+1}$) corresponds to an interval of length $l(e_{i})+2$.

We distinguish between two cases. If $pp^{\prime}\cap e_{i}=\emptyset$ (i.e.,
the second turn is before $\pi$ crosses $e_{i}$ again), as shown in Figure
6(a), then $pp^{\prime}$ does not intersect $e_{i+1}$, since this would imply
$l(e_{i})=l(e_{i+1})$. Therefore, $\pi$ reaches $e_{i+1}$ only after the turn
at $p^{\prime}$, and the tour $\pi^{\prime}$ which is obtained from $\pi$ by
deleting the link $pp^{\prime}$ (see Figure 6(b)), is a tour of $E$ of length
$|\pi|-1$, hence $\pi$ is not a minimum-link tour of $E$. Since our goal is to
find a minimum-link tour of $E$, we do not need to compute the interval on
$e_{i+1}$ formed by paths such as $\pi$ satisfying the condition above.

(a) A tour $\pi$ that passes through $a\in I(e_{i})$ (red), makes a turn in
orientation $\overline{c_{a}}$, and another turn in orientation $c_{j}$.

(b) The tour $\pi^{\prime}$ of length $|\pi|-1$, which is obtained by deleting
the link $pp^{\prime}$ from $\pi$.

Figure 6: Proof of Lemma 3. The case where the second turn is before $\pi$
crosses $e_{i}$ again.

If $pp^{\prime}\cap e_{i}\neq\emptyset$ (i.e., the second turn is not before
$\pi$ crosses $e_{i}$ again), let $T$ denote the region of all points that can
be reached by such paths, i.e., paths such as $\pi$ satisfying the condition
above (see the orange region in Figure 7(a)). Then $T\cap e_{i+1}$ is the
interval on $e_{i+1}$ with associated length $l(e_{i})+2$ and orientation
$c_{j}$, formed by these paths. But, by Lemma 1, there exists $b\in
I^{+}(e_{i},\overline{c_{a}})$ such that $a\subseteq b$ (see the blue interval
in Figure 7(b)), and clearly $T\subseteq\psi(b,c_{j})$, implying $T\cap
e_{i+1}\subseteq\psi(b,c_{j})\cap e_{i+1}$. The latter interval, i.e.,
$\psi(b,c_{j})\cap e_{i+1}$ is computed by our algorithm, so we do not need to
compute $T\cap e_{i+1}$.

(a) An interval $a$ (red) and the corresponding region $T$ (orange).

(b) An interval $b$ and the corresponding region $\psi(b,c_{j})$ (blue), which
contains $T$.

Figure 7: Proof of Lemma 3. The case where the second turn is not before $\pi$
crosses $e_{i}$ again.

###### Lemma 4

For any interval $a\in I(e_{i})$, any point $p\in\mathbb{R}^{2}$, and any
orientation $c_{j}\notin\\{c_{a},c_{a+1},c_{a-1}\\}$, $p$ can be reached by a
path that passes through $a$ and then makes a turn in some orientation
$c\neq\overline{c_{a}}$ and another turn in orientation $c_{j}$.

###### Proof

Consider any interval $a\in I(e_{i})$. Recall that
$\psi(a,\overline{c_{a}}_{+1})$ ($\psi(a,\overline{c_{a}}_{-1})$) denotes the
region of all the points that can be reached by a path that passes through $a$
and then makes a turn in orientation $\overline{c_{a}}_{+1}$
($\overline{c_{a}}_{-1}$) (see Figure 8). It is easy to see that
$\psi(a,c)\subseteq\psi(a,\overline{c_{a}}_{+1})$ for any
$c\in\phi(\overline{c_{a}},c_{a})$ and
$\psi(a,c)\subseteq\psi(a,\overline{c_{a}}_{-1})$ for any
$c\in\phi(c_{a},\overline{c_{a}})$. Therefore,
$\Delta_{a}=\psi(a,\overline{c_{a}}_{+1})\cup\psi(a,\overline{c_{a}}_{-1})$ is
the region of all the points that can be reached by a path that passes through
$a$ and then makes a turn in some orientation $c\neq\overline{c_{a}}$ (see
Figure 8(c)).

(a) An interval $a$ (red) and the region $\psi(a,\overline{c_{a}}_{+1})$
(blue).

(b) An interval $a$ (red) and the region $\psi(a,\overline{c_{a}}_{-1})$
(green).

(c) The region $\Delta_{a}$, which is the union of
$\psi(a,\overline{c_{a}}_{+1})$ and $\psi(a,\overline{c_{a}}_{-1})$.

Figure 8: All the points that can be reached by a path that passes through $a$
and then makes a turn in some orientation $c\neq\overline{c_{a}}$.

Consider any point $p\in\mathbb{R}^{2}$ and any orientation
$c_{j}\notin\\{c_{a},c_{a+1},c_{a-1}\\}$. If $p\in\Delta_{a}$, then $p$ can be
reached by a path that passes through $a$ and then makes a turn in some
orientation $c\neq\overline{c_{a}}$. By making an additional turn at $p$ in
orientation $c_{j}$ (without extending the path), we obtain a path that
reaches $p$ as required.

If $p\in\overline{\Delta_{a}}=\mathbb{R}^{2}\backslash\Delta_{a}$, then
$Ray(p,\overline{c_{j}})\cap\Delta_{a}\neq\emptyset$, since
$\overline{c_{j}}\notin\\{\overline{c_{a}}_{-1},\overline{c_{a}},\overline{c_{a}}_{+1}\\}$
(as shown in Figure 10). Let $p^{\prime}$ be any point on
$Ray(p,\overline{c_{j}})\cap\Delta_{a}$, then $p^{\prime}$ can be reached by a
path that passes through $a$ and then makes a turn in some orientation
$c\neq\overline{c_{a}}$, and by extending this path by adding the link
$p^{\prime}p$, we obtain a path that reaches $p$ as required.

Consider the region
$\Delta_{a}=\psi(a,\overline{c_{a}}_{+1})\cup\psi(a,\overline{c_{a}}_{-1})$
defined in the proof of Lemma 4. Then, as mentioned in the proof of Lemma 4,
$\Delta_{a}$ is the region of all the points that can be reached by a path
that passes through $a$ and then makes a turn in some orientation
$c\neq\overline{c_{a}}$. In addition, we notice that by extending such a path
by adding a link in orientation $c_{j}$, for
$c_{j}\in\\{c_{a},c_{a+1},c_{a-1}\\}$, we cannot leave $\Delta_{a}$ (see
Figure 10), since for any point $q\in\Delta_{a}$,
$Ray(q,c_{j})\subseteq\Delta_{a}$.

Figure 9: Lemma 4. If $p\in\overline{\Delta_{a}}$, then
$Ray(p,\overline{c_{j}})\cap\Delta_{a}\neq\emptyset$.

Figure 10: For any $q\in\Delta_{a}$,
$Ray(q,c_{j})\cap\overline{\Delta_{a}}=\emptyset$, for
$c_{j}\in\\{c_{a},c_{a+1},c_{a-1}\\}$.

The following claim bounds the number of intervals with associated length and
orientation $l(e_{i})+2$ and $c_{j}$, respectively, that are ‘created’ on
$e_{i+1}$.

###### Claim 4

At most $|I^{+}(e_{i},\overline{c_{j}})|+2$ intervals with associated length
and orientation $l(e_{i})+2$ and $c_{j}$, respectively, are ‘created’ on
$e_{i+1}$, during the execution of the algorithm.

###### Proof

The proof can be found in Appendix 0.A.3. Here, we only observe that there are
two ways to reach a point on $e_{i+1}$ with a path of length $l(e_{i})+2$
whose last link is of orientation $c_{j}$. The first is by passing through one
of the intervals $a\in I(e_{i})$ and then making two turns, where the first
one is in orientation $c\neq\overline{c_{a}}$ and the second one is in
orientation $c_{j}$ (see Lemma 3). The second way is by passing through one of
the intervals in $I^{+}(e_{i})\setminus I^{+}(e_{i},c_{j})$, and then making a
turn in orientation $c_{j}$. That is, the intervals on $e_{i+1}$ with
associated length $l(e_{i})+2$ and associated orientation $c_{j}$ are
determined by the intervals in $I(e_{i})\cup(I^{+}(e_{i})\setminus
I^{+}(e_{i},c_{j}))$.

The following claim bounds the number of intervals with associated length and
orientation $l(e_{i})+3$ and $c_{j}$, respectively, that are ‘created’ on
$e_{i+1}$.

###### Claim 5

For any $q\in e_{i+1}$ and for any $c_{j}\in C$, there exists a path of length
$l(e_{i})+3$ from $s$ to $q$, whose last link has orientation $c_{j}$, for
$1\leq i\leq n-1$.

###### Proof

Consider any path $\pi$ from $s$ to $e_{i}$ that corresponds to an interval in
$I(e_{i})$, and let $p$ be the point on $e_{i}$ where $\pi$ ends. Since $C$
spans the plane, there exists a two-link path from $p$ to $q$, and by making a
turn at $q$ in orientation $c_{j}$ (without extending the path), we obtain a
three-link path $\pi_{p,q}$ from $p$ to $q$ whose last link has orientation
$c_{j}$. So, the path obtained by concatenating the paths $\pi$ and
$\pi_{p,q}$ is as desired.

###### Claim 6

For any $0\leq i\leq n+1$ and $c_{j}\in C$, $|I(e_{i},c_{j})|\leq 2i+1$ and
$|I^{+}(e_{i},c_{j})|\leq 2i+1$.

###### Proof

The proof is by induction on $i$. For $i=0$, the claim is clearly true;
$|I(e_{0},c_{j})|=|I^{+}(e_{0},c_{j})|=1$.

Assume now that the claim is true for $i$, $0\leq i\leq n$, that is, for any
$c_{j}\in C$, we have $|I(e_{i},c_{j})|\leq 2i+1$ and
$|I^{+}(e_{i},c_{j})|\leq 2i+1$. We show below that it remains true for $i+1$.

Recall that $l(e_{i})\leq l(e_{i+1})\leq l(e_{i})+2$ (Claim 2). We show that
the claim remains true in each of the resulting three cases.

  * •

Case A: $l(e_{i+1})=l(e_{i})$. In this case $I(e_{i+1},c_{j})$ stores the
+0-intervals on $e_{i+1}$ with respect to $I(e_{i},c_{j})$. Since, each
interval $a\in I(e_{i},c_{j})$ ‘creates’ at most one +0-interval on $e_{i+1}$,
we get that $|I(e_{i+1},c_{j})|\leq|I(e_{i},c_{j})|\leq 2i+1$.

Recall that $I^{+}(e_{i+1},c_{j})$ is the set of maximal intervals on
$e_{i+1}$ formed by all paths of length $l(e_{i+1})+1=l(e_{i})+1$, whose last
link has orientation $c_{j}$. By Claim 3,
$|I^{+}(e_{i+1},c_{j})|\leq\max\\{|I(e_{i},\overline{c_{j}})|,|I^{+}(e_{i},c_{j})|\\}+2$,
and therefore $|I^{+}(e_{i+1},c_{j})|\leq\max\\{2i+1,2i+1\\}+2=2(i+1)+1$.

  * •

Case B: $l(e_{i+1})=l(e_{i})+1$. In this case, $I(e_{i+1},c_{j})$ is the set
of maximal intervals on $e_{i+1}$ formed by all paths of length
$l(e_{i+1})=l(e_{i})+1$, whose last link has orientation $c_{j}$. By Claim 3,
$|I(e_{i+1},c_{j})|\leq\max\\{|I(e_{i},\overline{c_{j}})|,|I^{+}(e_{i},c_{j})|\\}+2$,
so, $|I(e_{i+1},c_{j})|\leq\max\\{2i+1,2i+1\\}+2=2(i+1)+1$.

Now, $I^{+}(e_{i+1},c_{j})$ is the set of maximal intervals on $e_{i+1}$
formed by all paths of length $l(e_{i+1})+1=l(e_{i})+2$, whose last link has
orientation $c_{j}$. By Claim 4,
$|I^{+}(e_{i+1},c_{j})|\leq|I^{+}(e_{i},\overline{c_{j}})|+2$, and therefore
$|I^{+}(e_{i+1},c_{j})|\leq 2i+1+2=2(i+1)+1$.

  * •

Case C: $l(e_{i+1})=l(e_{i})+2$. In this case, $I(e_{i+1},c_{j})$ is the set
of maximal intervals on $e_{i+1}$ formed by all paths of length
$l(e_{i+1})=l(e_{i})+2$, whose last link has orientation $c_{j}$. Thus, by
Claim 4, $|I(e_{i+1},c_{j})|\leq|I^{+}(e_{i},\overline{c_{j}})|+2\leq
2(i+1)+1$. Moreover, in this case, $I^{+}(e_{i+1},c_{j})=\\{e_{i+1}\\}$, so
$|I^{+}(e_{i+1},c_{j})|=1$.

Running time. We bound the running time of each of the two stages of our
algorithm. Consider the $i$’th iteration of the main loop of Stage I. We need
$O(|I(e_{i},c_{j})|+|I^{+}(e_{i},c_{j})|)$ time to compute the $+0$-intervals
on $e_{i+1}$, $O(|I(e_{i})\setminus I(e_{i},c_{j})|+|I^{+}(e_{i})\setminus
I^{+}(e_{i},c_{j})|)$ time to compute the $+1$-intervals, and $O(|I(e_{i})|)$
time to compute the $+2$-intervals. Since we perform this calculation for each
$c_{j}\in C$, the running time of the i’th iteration is
$O(|C|\cdot\\{|I(e_{i})|+|I^{+}(e_{i})|\\})$. By Claim 6 we conclude that
$|I(e_{i})|=O(|C|\cdot(2i+1))$ and $|I^{+}(e_{i})|=O(|C|\cdot(2i+1))$, for
$1\leq i\leq n+1$. Therefore, the running time of Stage I is
$\sum_{i=1}^{n+1}O(|C|\cdot|C|\cdot(2i+1))=O(|C|^{2}\cdot n^{2})$.

In stage 2, we run Algorithm 1 for each $i$ from $n+1$ to $1$. The running
time of Algorithm 1 is $O(|I(e_{i-1})|+|I^{+}(e_{i-1})|)$, and by Claim 6 we
get $O(|C|\cdot i)$. Therefore, the running time of Stage II is
$\sum_{i=1}^{n+1}O(|C|\cdot i)=O(|C|\cdot n^{2})$.

Thus, the overall running time of the algorithm is $O(|C|^{2}\cdot n^{2})$, as
summarized:

###### Theorem 4.1

Given a set $E$ of $n$ disjoint $C$-oriented segments in the plane and points
$s$ and $t$ that do not belong to any of the segments in $E$, one can compute
a minimum-link $C$-oriented tour of $E$ in $O(|C|^{2}\cdot n^{2})$ time.

##  5 Extensions

In the case that $|C|=4$ (e.g., axis-parallel paths and segments), the
specialization of our analysis shows a constant upper bound on the number of
intervals on each segment; this results in overall time $O(n)$. Also, our
analysis only required that consecutive segments in $E$ do not intersect each
other; they can otherwise intersect. In ongoing and future work we consider
more general polygonal regions, possibly overlapping arbitrarily. We also
consider query versions of the problem in which we build data structures
(shortest path maps) that allow link distance queries on subsequences of the
input set of regions, between query points in the plane. Future work might
examine problems in 3D.

#### Acknowledgements

M. Katz was partially supported by the US-Israel Binational Science Foundation
(BSF project 2019715 / NSF CCF-2008551). J. Mitchell was partially supported
by the National Science Foundation (CCF-2007275) and the US-Israel Binational
Science Foundation (BSF project 2016116).

## References

  * [1] Sergey Alatartsev, Vera Mersheeva, Marcus Augustine, and Frank Ortmeier.  On optimizing a sequence of robotic tasks.  In 2013 IEEE/RSJ Internat. Conference on Intelligent Robots and Systems, pages 217–223. IEEE, 2013.
  * [2] Sergey Alatartsev, Sebastian Stellmacher, and Frank Ortmeier.  Robotic task sequencing problem: A survey.  J. of intelligent & robotic systems, 80:279–298, 2015.
  * [3] Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S. B. Mitchell.  Touring a sequence of polygons.  In Proc. of the 35th Annual ACM Symposium on Theory of Computing, 2003, pages 473–482. ACM, 2003.
  * [4] Peter Egyed and Rephael Wenger.  Ordered stabbing of pairwise disjoint convex sets in linear time.  Discrete Applied Mathematics, 31(2):133–140, 1991.
  * [5] Leonidas J. Guibas, John Hershberger, Joseph S. B. Mitchell, and Jack Snoeyink.  Approximating polygons and subdivisions with minimum link paths.  Internat. J. on Computational Geometry and Applications, 3(4):383–415, 1993.
  * [6] Maarten Löffler.  Existence and computation of tours through imprecise points.  Internat. J. on Computational Geometry and Applications, 21(1):1–24, 2011.
  * [7] Joseph S. B. Mitchell.  Shortest paths and networks.  In Jacob E. Goodman Csaba Tóth, Joseph O’Rourke, editor, Handbook of Discrete and Computational Geometry (3rd Edition), chapter 31, pages 811–848. Chapman & Hall/CRC, Boca Raton, FL, 2017.
  * [8] Joseph S. B. Mitchell, Valentin Polishchuk, and Mikko Sysikaski.  Minimum-link paths revisited.  Computational Geometry, 47(6):651–667, 2014.
  * [9] Gabriele Neyer.  Line simplification with restricted orientations.  In Workshop on Algorithms and Data Structures, pages 13–24. Springer, 1999.
  * [10] Bettina Speckmann and Kevin Verbeek.  Homotopic $C$-oriented routing with few links and thick edges.  Computational Geometry, 67:11–28, 2018.

##  Appendix 0.A Details

###  0.A.1 Stage II

In this stage we use the information collected in the first stage to construct
a minimum-link tour $\pi$ of $E$.

We construct $\pi$ incrementally beginning at $t$ and ending at $s$. That is,
in the first iteration we add the portion of $\pi$ from $t$ to $e_{n}$, in the
second iteration we add the portion from $e_{n}$ to $e_{n-1}$, etc. Assume
that we have already constructed the portion of $\pi$ from $t$ to $e_{i}$,
where this portion ends at point $p$ of interval $a$ on $e_{i}$. We describe
in Algorithm 1 how to compute the portion from $e_{i}$ to $e_{i-1}$, which
begins at point $p$ of $a$ and ends at a point $p^{\prime}$ of interval $b$ on
$e_{i-1}$ (where $b\in I(e_{i-1})\cup I^{+}(e_{i-1})$) and consists of
$l_{a}-l_{b}+1$ links. Before continuing to the next iteration, we set
$p=p^{\prime}$ and $a=b$.

After adding the last portion, which ends at $s$, we remove all the redundant
vertices from $\pi$, i.e., vertices at which $\pi$ does not make a turn.

Input : Index $i$, an interval $a$ on $e_{i}$, a point $p\in a$

Output : An interval $b$ on $e_{i-1}$, a point $p^{\prime}\in b$ and a
$C$-oriented path $\pi_{p,p^{\prime}}$ from $p$ to $p^{\prime}$ consisting of
$l_{a}-l_{b}+1$ links

begin

if  _$l_{a}=l(e_{i-1})$_ then

$p^{\prime}\leftarrow Ray(p,\overline{c_{a}})\cap e_{i-1}$ and
$\pi_{p,p^{\prime}}\leftarrow(p,p^{\prime})$;

$b\leftarrow$ the interval of $I(e_{i-1},c_{a})$ containing $p^{\prime}$;

Stop and return $p^{\prime},b$ and $\pi_{p,p^{\prime}}$;

if  _$l_{a}=l(e_{i-1})+1$_ then

if  _$Ray(p,\overline{c_{a}})\cap e_{i-1}\neq\emptyset$_ then

$p^{\prime}\leftarrow Ray(p,\overline{c_{a}})\cap e_{i-1}$ and
$\pi_{p,p^{\prime}}\leftarrow(p,p^{\prime})$;

$b\leftarrow$ the interval of $I^{+}(e_{i-1},c_{a})$ containing $p^{\prime}$;

Stop and return $p^{\prime},b$ and $\pi_{p,p^{\prime}}$;

else

foreach  _$d\in I(e_{i-1})\backslash I(e_{i-1},c_{a})$_ do

if  _$Ray(p,\overline{c_{a}})\cap PT(d)\neq\emptyset$_ then

$q\leftarrow$ any point in $Ray(p,\overline{c_{a}})\cap PT(d)$;

$p^{\prime}\leftarrow Ray(q,\overline{c_{d}})\cap e_{i-1}$;

$\pi_{p,p^{\prime}}\leftarrow(p,q,p^{\prime})$ and $b\leftarrow d$;

Stop and return $p^{\prime},b$ and $\pi_{p,p^{\prime}}$;

if  _$l_{a}$ = $l(e_{i-1})+3$_ then

$a\leftarrow$ any interval in $I(e_{i})$ that contains $p$;

if  _$l_{a}=l(e_{i-1})+2$_ then

foreach  _$d\in I^{+}(e_{i-1})\backslash I^{+}(e_{i-1},c_{a})$_ do

if  _$Ray(p,\overline{c_{a}})\cap PT(d)\neq\emptyset$_ then

$q\leftarrow$ any point in $Ray(p,\overline{c_{a}})\cap PT(d)$;

$p^{\prime}\leftarrow Ray(q,\overline{c_{d}})\cap e_{i-1}$;

$\pi_{p,p^{\prime}}\leftarrow(p,q,p^{\prime})$ and $b\leftarrow d$;

Stop and return $p^{\prime},b$ and $\pi_{p,p^{\prime}}$;

foreach  _$d\in I(e_{i-1})$_ do

if
_$Ray(p,\overline{c_{a}})\cap(\psi(d,\overline{c_{d}}_{+1})\cup\psi(d,\overline{c_{d}}_{-1}))\neq\emptyset$_
then

$v\leftarrow$ any point in
$Ray(p,\overline{c_{a}})\cap(\psi(d,\overline{c_{d}}_{+1})\cup\psi(d,\overline{c_{d}}_{-1}))$;

if  _$Ray(v,c_{d+1})\cap PT(d)\neq\emptyset$_ then

$q\leftarrow$ any point in $Ray(v,c_{d+1})\cap PT(d)$;

$p^{\prime}\leftarrow Ray(q,\overline{c_{d}})\cap e_{i-1}$, $b\leftarrow d$;

else

$q\leftarrow$ any point in $Ray(v,c_{d-1})\cap PT(d)$;

$p^{\prime}\leftarrow Ray(q,\overline{c_{d}})\cap e_{i-1}$, $b\leftarrow d$;

$\pi_{p,p^{\prime}}\leftarrow(p,v,q,p^{\prime})$;

Stop and return $p^{\prime},b$ and $\pi_{p,p^{\prime}}$;

Algorithm 1 SubPath Recovery

###  0.A.2 Proof of Claim 3: For any interval $h\in
I(e_{i},\overline{c_{j}}$), $PT(h)\cap e_{i+1}=\emptyset$

If Case A: If $e_{i+1}$ intersects at most one of the chains $l_{A}$ and
$l_{D}$, then, as in Case A above, at most two intervals are formed on
$e_{i+1}$, where each of them contains an endpoint of $e_{i+1}$ (see Figure
4(a)).

If, however, $e_{i+1}$ intersects both $l_{A}$ and $l_{D}$ (which is possible
since now $e_{i+1}$ may intersect $PT(b)$), then it intersects each of them
exactly once (otherwise, we get that $e_{i+1}\cap b\neq\emptyset$), and a
single interval is formed on $e_{i+1}$, which does not contain an endpoint of
$e_{i+1}$ (see Figure 5(a)).

If Case B: If $e_{i+1}$ intersects $l_{B}$ and $l_{D}$ in more than two points
(in total), then it must also intersect $b$, which is impossible. Therefore,
$e_{i+1}$ can intersect $l_{B}$ and $l_{D}$ in at most two points (in total),
and at most two intervals are formed on $e_{i+1}$, where each of them contains
an endpoint of $e_{i+1}$ (see Figure 5(b)).

If Case C: Since Case B and Case C are symmetric, at most two intervals are
formed on $e_{i+1}$, each of which contains an endpoint of $e_{i+1}$.

If Case D: Identical to Case D above, that is, $e_{i+1}$ intersects $l$ either
at one or at two points, and at most two intervals are formed on $e_{i+1}$,
each of which contains an endpoint of $e_{i+1}$ (see Figure 4(b)).

We have shown that by passing through an interval in
$\\{b\\}\cup\delta(b)\setminus I(e_{i},\overline{c_{j}})$, at most one
interval that does not contain an endpoint of $e_{i+1}$ is formed on
$e_{i+1}$, or at most two intervals (with associated length $l(e_{i})+1$ and
orientation $c_{j}$) are formed on $e_{i+1}$, where each of them contains an
endpoint of $e_{i+1}$.

Therefore, the total number of such intervals that are formed on $e_{i+1}$, by
passing through an interval in $\bigcup_{b\in
I^{+}(e_{i},c_{j})}\\{b\\}\cup\delta(b)\setminus I(e_{i},\overline{c_{j}})$ is
at most $|I^{+}(e_{i},c_{j})|+2$. (For each endpoint $p$ of $e_{i+1}$, we
retain only the longest interval with $p$ as one of its endpoints.)

Finally, observe that by passing through an interval $h\in
I(e_{i},\overline{c_{j}})$ and turning backwards in orientation $c_{j}$, at
most one interval is formed on $e_{i+1}$. However, since $PT(h)\cap
e_{i+1}=\emptyset$, the interval formed on $e_{i+1}$ is contained in
$PT(b)\cap e_{i+1}$ and will therefore not appear in the returned set of
intervals formed on $e_{i+1}$.

We conclude that at most $|I^{+}(e_{i},c_{j})|+2$ intervals (with associated
length $l(e_{i})+1$ and orientation $c_{j}$) are formed on $e_{i+1}$ during
the execution of the algorithm (in the case that for any interval $h\in
I(e_{i},\overline{c_{j}}$), $PT(h)\cap e_{i+1}=\emptyset$).

###  0.A.3 Proof of Claim 4

###### Proof

There are two ways to reach a point on $e_{i+1}$ with a path of length
$l(e_{i})+2$ whose last link is of orientation $c_{j}$. The first is by
passing through one of the intervals $a\in I(e_{i})$ and then making two
turns, where the first one is in orientation $c\neq\overline{c_{a}}$ and the
second one is in orientation $c_{j}$ (see Lemma 3). The second way is by
passing through one of the intervals in $I^{+}(e_{i})\setminus
I^{+}(e_{i},c_{j})$, and then making a turn in orientation $c_{j}$. That is,
the intervals on $e_{i+1}$ with associated length $l(e_{i})+2$ and associated
orientation $c_{j}$ are determined by the intervals in
$I(e_{i})\cup(I^{+}(e_{i})\setminus I^{+}(e_{i},c_{j}))$.

First, if there is an interval $a\in I(e_{i})$ such that
$c_{j}\notin\\{c_{a-1},c_{a},c_{a+1}\\}$, then, by Lemma 4,
$R_{a}=\mathbb{R}^{2}$, where $R_{a}$ is the region of all the points that can
be reached by a path that passes through $a$ and then makes two turns, where
the first is in orientation $c\neq\overline{c_{a}}$ and the second is in
orientation $c_{j}$. Thus, $R_{a}\cap e_{i+1}=e_{i+1}$ and only one interval
is formed on $e_{i+1}$.

Assume therefore that for each interval $a\in I(e_{i})$, we have
$c_{j}\in\\{c_{a-1},c_{a},c_{a+1}\\}$. Now, fix an interval $a\in I(e_{i})$,
then $R_{a}=\Delta_{a}$ (as observed in the paragraph following Lemma 4).
Consider an interval $b\in
I^{+}(e_{i})\setminus\\{I^{+}(e_{i},\overline{c_{j}})\cup
I^{+}(e_{i},c_{j})\\}$ (we will treat the case $b\in
I^{+}(e_{i},\overline{c_{j}})$ separately), and set $R_{a\cup
b}=R_{a}\cup\psi(b,c_{j})$. Then $R_{a\cup b}\cap e_{i+1}$ gives us the
intervals on $e_{i+1}$ with length $l(e_{i})+2$ and orientation $c_{j}$, which
are formed by passing through $a$ or $b$.

Next, we characterize the region $R_{a\cup b}$, by considering several cases.

Case A: $PT(b)\subseteq\Delta_{a}$ (see Figure 11(a)).
Since for any $q\in\Delta_{a}$, $Ray(q,c_{j})\subseteq\Delta_{a}$, we have
$\psi(b,c_{j})=\bigcup_{q\in PT(b)}Ray(q,c_{j})\subseteq\Delta_{a}$, and
therefore $R_{a\cup b}=\Delta_{a}$.

Case B: $PT(b)\not\subseteq\Delta_{a}$ and
$c_{b}\notin\\{\overline{c_{a}}_{-1},\overline{c_{a}},\overline{c_{a}}_{+1}\\}$
(see Figure 11(b)).
In this case, $R_{a\cup b}$ is the union of $\Delta_{a}$ and the triangle that
is formed by the rays defining $\Delta_{a}$ and the appropriate side of
$PT(b)$; see the yellow triangle denoted $\Delta_{b}$ in Figure 11(b).

(a) Case A.

(b) Case B.

Figure 11: $R_{a\cup b}$ in Cases A and B.

Case C: $PT(b)\not\subseteq\Delta_{a}$ and
$c_{b}\in\\{\overline{c_{a}}_{-1},\overline{c_{a}},\overline{c_{a}}_{+1}\\}$
(see Figure 12).
Assume, e.g., that $c_{b}=\overline{c_{a}}_{+1}$. Then,
$c_{j}\in\\{c_{a-1},c_{a}\\}$ (since $b\notin I^{+}(e_{i},\overline{c_{j}})$).
In this case, $R_{a\cup b}$ is the union of $\Delta_{a}$ and the ‘trapezoid’
that is formed by the rays defining $\Delta_{a}$ and the appropriate side of
$PT(b)$; see the yellow region $\Delta_{b}$ in Figure 12(a). The subcases
$c_{b}=\overline{c_{a}}_{-1}$ and $c_{b}=\overline{c_{a}}$ are similar and are
depicted in Figure 12(b) and Figures 12(c) and 12(d), respectively.

(a) $c_{b}=\overline{c_{a}}_{+1}$ and $c_{j}\in\\{c_{a-1},c_{a}\\}$.

(b) $c_{b}=\overline{c_{a}}_{-1}$ and $c_{j}\in\\{c_{a+1},c_{a}\\}$.

(c) $c_{b}=\overline{c_{a}}$ and $c_{j}=c_{a-1}$.

(d) $c_{b}=\overline{c_{a}}$ and $c_{j}=c_{a+1}$.

Figure 12: $R_{a\cup b}$ in Case C. Figure 13: $e_{i+1}$ intersects $R_{a\cup
b}$’s boundary either at a single point $q$ or at two points $p$ and
$p^{\prime}$.

We conclude that in each of the cases A–C, $R_{a\cup b}$ is bounded by an
infinite convex chain $l$ consisting of at most three edges (see the red chain
in Figure 13). But this implies that, unless $R_{a\cup b}\cap e_{i+1}$ is
$e_{i+1}$ or is empty, $R_{a\cup b}\cap e_{i+1}$ consists of at most two
intervals, each of which contains an endpoint of $e_{i+1}$ (see edges
$e^{1}_{i+1}$ and $e^{2}_{i+1}$ in Figure 13).

We have shown that by passing through the intervals $a$ and $b$, at most two
intervals (with associated length $l(e_{i})+2$ and orientation $c_{j}$) are
formed on $e_{i+1}$. Moreover, each of these intervals contains an endpoint of
$e_{i+1}$. Therefore, the total number of such intervals that are formed on
$e_{i+1}$, by passing through the intervals in $I(e_{i})\cup
I^{+}(e_{i})\setminus\\{I^{+}(e_{i},\overline{c_{j}})\cup
I^{+}(e_{i},c_{j})\\}$ is at most two (for each endpoint $p$ of $e_{i+1}$, we
retain only the longest interval with $p$ as one of its endpoints).

Finally, observe that by passing through an interval in
$I^{+}(e_{i},\overline{c_{j}})$ and turning backwards in orientation $c_{j}$,
at most one interval is formed on $e_{i+1}$, which does not necessarily
contain an endpoint of $e_{i+1}$.

We conclude that at most $|I^{+}(e_{i},\overline{c_{j}})|+2$ intervals (with
associated length $l(e_{i})+2$ and orientation $c_{j}$) are formed on
$e_{i+1}$ during the execution of the algorithm.


* a fixed point of $F$ if there is an isomorphism $f:x\to Fx$ in $\mathbb X_{\circ}$.

(1) Trivially, a fixed point of $F$ is both, a forward fixed point and a backward fixed point of $F$. By Facts <ref>(2), if $\mathbb X$ is forward (backward) symmetric, every forward (backward, respectively) fixed point of $F$ is already a fixed point of $F$.

(2) Here is a normed functor $F$ of a normed category $\mathbb X$ in which every object is a forward fixed point of $F$, but which has no backward fixed point of $F$: consider $\mathbb X=\mathrm  iX$ for $X=\{0,1,2, ...\}$ with $X(m,n)=0$ for $m\leq n$ and $X(m,n)=1$ otherwise, and let $F$ be given by $Fn=n+1$ for all $n$. (Note that $F$ is even norm preserving.)

(3) For $X$ as in (2), considering $\mathbb X=\mathrm{i}(X\otimes X^{\mathrm{op}})$ and its normed endofunctor $F\otimes F^{\mathrm{op}}$, we have (infinitely many) simultaneously  forward and backward fixed points of $F\otimes F^{\mathrm{op}}$, but no fixed point.

For a $\V$-normed endofunctor $F:\mathbb X\to\mathbb X$, let us first consider any morphism $f:x\to Fx$ and form the iteration sequence $s_f$ of $f$:

$$\xymatrix{x\ar[r]^f & Fx\ar[r]^{Ff} & F^2x\ar[r]^{F^2f} & F^3x\ar[r]^{F^3f}& ... \\}.$$

Assuming that, at the ordinary category level, there is a colimit cocone $\gamma_f:s_f\to \Delta y$ in $\mathbb X$, we obtain a comparison morphism $\overline{f}:y\to Fy$ with $\Delta\overline{f}\cdot\gamma_f=F\gamma_f$, which is an isomorphism precisely when the (ordinary) functor $F$ preserves the colimit. Assuming further that $\gamma_f$ actually exhibits $y$ as a normed colimit of $s_f$, since $F$ is $\V$-normed, in the terminology of Lemma <ref> not only $\gamma_f$ must be $\kk$-cocone, but also $F\gamma_f$, so that with property (C2b) of Corollary <ref> one concludes that $\overline{f}$ must be $\kk$-morphism:

$$|\overline{f}|\geq\bigvee_N\bigwedge_{n\geq N}|\overline{f}\cdot(\gamma_f)_n|=\bigvee_N\bigwedge_{n\geq N}|F(\gamma_f)_n|\geq\bigvee_N\bigwedge_{n\geq N}|(\gamma_f)_n|\geq\kk\;.$$

Furthermore, if  $F$ preserves $y$ as a normed colimit of $s_f$, then trivially also $\overline{f}^{-1}$ must be a $\kk$-morphism. This normed preservation of the colimit $y$ is particularly guaranteed if $\mathbb X$ is forward or backward symmetric, since  with Facts <ref>(2) and the proof of Corollary <ref> we again obtain that  $\overline{f}^{-1}$ is $\kk$-morphism.

In summary, we proved:

Let $F:\mathbb X\to\mathbb X$  be a $\V$-normed functor preserving ordinary colimits of sequences, and let $f:x\to Fx$ be a morphism for which the iterated sequence $s_f$ has a normed colimit $y$ in $\mathbb X$. Then $y$ is a forward fixed point of $F$ in $\mathbb X$, and it is even a fixed point if $F$ preserves the colimit $y$ as a normed colimit, in particular if  $\mathbb X$ is forward or backward symmetric.

We now consider $\V=\mathcal R_+$ and provide a sufficient condition à la Banach for the existence of a normed colimit of the iterated sequence of a morphism $x\to Fx$, for a contractive functor $F:\mathbb X\to \mathbb X$, so that there is a (non-negative) Lipschitz factor $L< 1$, i.e., $|Fh|\leq L |h|$ for all morphisms $h$ in $\mathbb X$.

Let $\mathbb X$ be a Cauchy cocomplete normed category, and let $F:\mathbb X\to \mathbb X$ be a contractive functor which preserves (ordinary) colimits of sequences. Then, if $\mathbb X$ contains any morphism $f:x\to Fx$ with $|f|<\infty$, then $\mathbb X$ contains a forward fixed point of $F$, and even a fixed point of $F$ if $F$ preserves normed colimits of Cauchy sequences; in particular, if $\mathbb X$ is forward or backward symmetric.

In light of the Proposition, it suffices to show that the iterated sequence $s_f$ of the given morphism $f$ with $|f|<\infty$ is Cauchy. This, however, follows just like in the classical case of a contraction of a metric space from the Cauchyness of the geometric series given by $L$: indeed, for all $m\leq n$ one has

$$|(s_f)_{m,n}:F^mx\to F^nx|= |F^{n-1}f\cdot ...\cdot F^mf|\leq(L^{n-1}+\dots+L^m)|f|\;.                  $$

(1) The classical Banach Fixed Point Theorem for the contraction $\varphi$ of a (non-empty) complete (classical) metric space $X$ follows when we consider $\mathbb X=\mathrm i X$ and $F=\mathrm i\varphi$.

(2) One cannot expect the uniqueness statement for fixed points in the classical metric case to extend verbatim to normed categories, not even for Lawvere metric spaces: just consider the coproduct in $\mathsf{Met}_1$ of two copies of the Euclidean line. However, the classical uniqueness is an obvious consequence of the following general statement: Suppose we are given a forward fixed point $x$ and a backward fixed point $y$ of the contraction $F:\mathbb X\to\mathbb X$, with the property that the minimum
$$\min\{|h|\mid h:x\to y \text{ in }\mathbb X\}$$
exists and is positive;
then such minimal morphism $h_0$ must be a $0$-isomorphism. Indeed, since we have isomorphisms $f:x\to Fx$ and $g:Fy\to y$ with $|f|=0=|g|$, the minimality of $|h_0|$ forbids $|h_0|>0$, as this would imply

$$|h_0|\leq|g\cdot Fh_0\cdot f|\leq |g|+|Fh_0|+|f|=|Fh_0|<|h_0|\;.$$

(3) Theorem <ref> improves Kubiś's Corollary 4.2 in [29], since the normed sequential colimits considered there are not necessarily unique up to $0$-isomorphism: see Facts <ref>(3). Actually, we have not been able to establish a valid proof of Kubi$\check{\mathrm s}$'s version of the Banach Fixed Point Theorem since, in the absence of Condition (C2b), one cannot argue as in our proof of Proposition <ref>.

§ APPENDIX: CONDITION A VS. CONDITION B

For a (unital and commutative) quantale $\V=(\V,\leq,\otimes,\kk)$, we show the logical independence of conditions (A) and (B) of Section <ref>, i.e., of the conditions

$$\text{(A)}\quad\kk=\bigvee\{u\in\V \mid u\ll\kk\}\qquad\text{and}\qquad\text{(B)}\quad\kk\wedge(-):\V\to\V\quad\text{preserves arbitrary joins}.$$

It suffices to find an integral quantale which does not satisfy (A) (see Remarks <ref>(2)). This is not hard; for example, for any infinite set $X$, consider the cofinite topology $\mathcal{O}(X)$ on $X$ (so that a non-empty subset $U\subseteq X$ is open precisely when $X\setminus U$ is finite) as a quantale ($\mathcal{O}(X),\subseteq,\cap, X)$. Then any open set $U$ with $U\ll X$ must be empty since, otherwise, the finiteness of $X\setminus U$ makes the infinite set $X$ satisfy

$$X=\bigcup_{x\in U}X\setminus\{x\},$$

whereas no $x\in U$ allows $U\subseteq X\setminus\{x\}$. Consequently, (A) is violated in $\mathcal O(X)$.

$\text{(A)}\nRightarrow\text{(B)}$ (see [18]):

Consider the $3$-element cyclic group $Z_3=(\{0,1,2\},+)$ as a discretely ordered set. Its MacNeille completion adds the top and bottom elements $\top$ and $\bot$ to it, giving the complete $5$-element diamond lattice $M_3$, with atoms $0,1,2$.  This lattice carries the operation $\otimes$ of a quantale which coincides with $+$ when  restricted to $Z_3$, and which satisfies $\top\otimes\alpha=\top$ (and necessarily $\bot\otimes\alpha=\bot$) for all $\alpha\in M_3,\;\alpha\neq\bot$. Finally we extend the lattice $M_3$ by two new elements, $\kk$ and
$\overline{\top}$, to obtain the desired $7$-element quantale $\overline{M}_3$ satisfying (A) but not (B). Its quantalic operation $\otimes$ extends the tensor product of $M_3$ and makes $\kk$ a new tensor-neutral element in $\overline{M}_3$, above only $0$ and $\bot$, while $\overline{\top}$ becomes a new top element in $\overline{M}_3$; tensoring by $\overline{\top}$ is defined by $\overline{\top}\otimes\overline{\top}=\overline{\top}$ and $ \overline{\top}\otimes\alpha=\top$ for all $\alpha\in\overline{M}_3,\alpha\neq\bot$.

$\xymatrix{ & \overline{\top}\ar@{-}[d]\ar@{-}[rd] & \\
& \top\ar@{-}[ld]\ar@{-}[d]\ar@{-}[rd] & \kk\ar@{-}[ld]\\
1\ar@{-}[rd] & 0\ar@{-}[d] & 2\ar@{-}[ld] \\
& \bot}$

$\otimes$   $\overline{\top}$   $\kk$   $\top$   0   1   2   $\bot$

$\overline{\top}$   $\overline{\top}$   $\overline{\top}$   $\top$   $\top$   $\top$   $\top$   $\bot$

$\kk$   $\overline{\top}$   $\kk$   $\top$   0   1   2   $\bot$

$\top$   $\top$   $\top$   $\top$   $\top$   $\top$   $\top$   $\bot$

0   $\top$   0   $\top$   0   1   2   $\bot$

1   $\top$   1   $\top$   1   2   0   $\bot$

2   $\top$   2   $\top$   2   0   1   $\bot$

$\bot$   $\bot$   $\bot$   $\bot$   $\bot$   $\bot$   $\bot$   $\bot$

(1) Following a question posed at the occasion of the second-named author's presentation of some of the results of this paper at the Portuguese Category Seminar in October 2023, a first witness for $\text{(A)}\nRightarrow\text{(B)}$ was communicated  to the authors shortly afterwards by Javier Gutiérrez-García. His subsequent paper [18] with Ulrich Höhle comprehensively analyzes and characterizes many types of quantales with $\text{(A)}\nRightarrow\text{(B)}$, even in the context of not necessarily commutative or unital quantales. The above example of a quantale witnessing $\text{(A)}\nRightarrow\text{(B)}$ is smallest with that property, but there are other such $7$-element quantales. Remarkably, it is also shown in [18] that the procedure of finding counterexamples as sketched here starting with the group $Z_3$ may in fact be followed with any group $G$ of at least 3 elements instead.

(2) There are many infinite topological spaces $X$ (other than those carrying the cofinite topology) such that $\mathcal O(X)$ witnesses $\text{(B)}\nRightarrow\text{(A)}$, but none of them can be Alexandroff (so that $\mathcal O(X)$ would be closed under arbitrary intersection). Indeed, one easily verifies that the quantale $\mathcal O(X)$ is completely distributive for every Alexandroff space $X$.
Other types of integral quantales satisfying (B) but violating (A) include those complete MV-algebras whose underlying lattice fails to be completely distributive. Indeed, by Proposition 3.13 of [17], such MV-algebras must fail condition (A).

[1]
J. Adámek, H. Herrlich, G.E. Strecker.
Abstract and Concrete Categories.
John Wiley & Sons, New York, 1990.
Republished in: Reprints in Theory and Applications of Categories 17, 2006.

[2]
J. Adámek, M. Hu$\check{\mathrm s}$ek, J. Rosický, W. Tholen.
Smallness in Topology.
Quaestiones Mathematicae 46:13–39, 2023.

[3]
J. Adámek and J. Rosický.
Locally Presentable and Accessible Categories.
Cambridge University Press, Cambridge, 1994.

[4]
A. Akhvlediani, M.M. Clementino, W. Tholen.
On the categorical meaning of Hausdorff and Gromov distances, I.
Topology and its Applications 157:1275–1295, 2010.

[5]
M.H. Albert and G.M. Kelly.
The closure of a class of colimits.
Journal of Pure and Applied Algebra 51:1–17, 1988.

[6]
P.N. Ánh and R. Wiegandt.
Compactness in categories and interpretations. In:
S.K. Jain and S. Tariq Rizvi (editors), Advances in Ring Theory.
Springer, New York, 1997, pp. 17–30.

[7]
R. Betti and M. Galuzzi.
Categorie normate.
Bollettino dell’Unione Matematica Italiana 4(11):66–75, 1975.

[8]
N.H. Bingham and A.J. Ostaszewski.
Normed versus topological groups: dichotomy and duality.
Dissertationes Mathematicae 472:1–138, 2010.

[9]
M.M. Bonsangue, F. van Breugel, J.J.M. Rutten.
Generalized metric spaces: Completion, topology, and powerdomains via the Yoneda embedding.
Theoretical Computer Science 193:1–51, 1998.

[10]
F. Borceux and D. Dejean.
Cauchy completion in category theory.
Cahiers de Topologie Géometrie Différentielle Catégoriques 27:133–146, 1986.

[11]
N. Bourbaki.
Elements of Mathematics. General Topology, Part 1.
Springer. English translation from French, originally published by Hermann, Paris, 1966.

[12]
B. Bubenik, V. de Silva, J. Scott.
Interleaving and Gromov-Hausdorff distances.
arXiv:1707.06288 [mathCT], 2017.

[13]
R.C. Flagg, Completeness in continuity spaces.
In: R.A.G. Seely (editor), Category Theory 1991: Proceedings of the International Summer Category Theory Meeting, Montreal 1991, vol. 13 of CMS Conference Proceedings, American Mathematical Society, Providence R.I., 1992.

[14]
R.C. Flagg.
Quantales and continuity spaces.
Algebra Universalis 37(3):257–276, 1997.

[15]
P. Gabriel and F. Ulmer.
Lokal präsentierbare Kategorien.
Lecture Notes in Mathematics 221, Springer-Verlag, Berlin, 1971.

[16]
M.  Grandis.
Categories, norms and weights.
Journal of Homotopy and Related Structures 2(2):171–186, 2007.

[17]
J. Gutiérrez-García, U. Höhle, T. Kubiak.
A theory of quantale-enriched dcpos and their topologization.
Fuzzy Sets and Systems 444:103–130, 2022.

[18]
J. Gutiérrez-García and U. Höhle.
Unitally nondistributive quantales.
arXiv:2402.17284 [math.GN], 2024.

[19]
J. Hemelaer and M. Rogers.
Geometric morphisms between toposes of monoiod actions: factorization systems.
Theory and Applications of Categories 40(4):80–129, 2024.

[20]
D. Hofmann and P. Nora.
Hausdorff coalgebras.
Applied Categorical Structures 28:773–806, 2020.

[21]
D. Hofmann and C.D. Reis.
Probabilistic metric spaces as enriched categories.
Fuzzy Sets and Systems 210:1–21, 2013.

[22]
D. Hofmann, G.J. Seal, W. Tholen (editors).
Monoidal Topology. A Categorical Approach to Order, Metric, and Topology.
Cambridge University Press, Cambridge, 2014.

[23]
D. Hofmann and W. Tholen.
Lawvere completion via closure.
Applied Categorical Structures 18:259–287, 2010.

[24]
M. Insall and D. Luckhardt.
Norms on categories and analogs of the Schröder-Bernstein Theorem.
arXiv:2105.06832v2 [math.CT], 2021.

[25]
J.R. Isbell.
Epimorphisms and dominions.
In: S. Eilenberg, D.K. Harrison, S. Mac Lane, H. Röhrl (editors), Proceedings of the Conference on Categorical Algebra, La Jolla 1965, Springer, New York, 1966, pp. 232–246.

[26]
G.M. Kelly.
Basic Concepts of Enriched Category Theory.
Cambridge University Press, Cambridge, 1982.
Republished in: Reprints in Theory and Applications of Categories 10, 2005.

[27]
G.M. Kelly and S. Lack.
$\V$-Cat is locally presentable or locally bounded if $\V$ is so.
Theory and Applications of Categories 8(23):555–575, 2001.

[28]
G.M. Kelly and V. Schmitt.
Notes on enriched categories with colimits of some class.
Theory and Applications of Categories 14(17):399–423, 2005.

[29]
W. Kubiś.
Categories with norms.
arXiv:1705.10189v1 [math.CT], 2017.

[30]
F.W. Lawvere.
Metric spaces, generalized logic, and closed categories.
Rendiconti del Seminario Matematico e Fisico di Milano 43:135–166, 1973.
Republished in: Reprints in Theory and Applications of Categories 1, 2002.

[31]
F.W. Lawvere.
Taking categories seriously.
Revista Colombiana de Matemáticas 20:147–178, 1986.
Republished in: Reprints in Theory and Applications of Categories 8, 2005.

[32]
F. Loregian.
(Co)end Calculus.
Cambridge University Press, Cambridge, 2021.

[33]
S. Mac Lane.
Categories for the Working Mathematician, Second Edition.
Springer-Verlag, New York, 1998.

[34]
A. Neeman.
Metrics on triangulated categories.
Journal of Pure and Applied Algebra 224(4):106206, 2020.

[35]
P. Perrone.
Lifting couplings in Wasserstein spaces.
Logic in Computer Science DOI:arXiv2110.06591v2 [mathCT], 2021.

[36]
I. Stubbe.
“Hausdorff distance” via conical cocompletion.
Cahiers de Topologie Géometrie Différentielle Catégoriques 51(1):51–76, 2010.

[37]
W. Tholen.
Amalgamations in categories.
Algebra Universalis 14:391–397, 1982.

[38]
W. Tholen.
Lax distributive laws for topology, I.
Cahiers de Topologie Géometrie Différentielle Catégoriques 60(3):311–364, 2019.

[39]
S. Vickers.
Localic completion of generalized metric spaces. I.
Theory and Applications of Categories 14(15):328–356, 2005.

[40]
R.J. Wood.
Ordered sets via adjunction.
In: M.C. Pedicchio, W. Tholen (editors), Categorical Foundations, Cambridge University Press, Cambridge, 2004, pp. 5–47.