This work is supported by the French ANR PRC grant ADDS (ANR-19-CE48-0005).
Aix-Marseille Université and LIS, France<EMAIL_ADDRESS>https://orcid.org/0000-0002-9807-028X Université Clermont Auvergne and LIMOS,
France<EMAIL_ADDRESS>https://orcid.org/0000-0002-2664-0650 Université
Clermont Auvergne and LIMOS, France<EMAIL_ADDRESS>https://orcid.org/0000-0001-5985-2169 Guilherme D. da Fonseca, Yan Gerard, and
Bastien Rivier Theory of computation Computational geometry

# Short Flip Sequences to
Untangle Segments in the Plane

Guilherme D. da Fonseca  Yan Gerard  Bastien Rivier

###### Abstract

A (multi)set of segments in the plane may form a TSP tour, a matching, a tree,
or any multigraph. If two segments cross, then we can reduce the total length
with the following _flip_ operation. We _remove_ a pair of crossing segments,
and _insert_ a pair of non-crossing segments, while keeping the same vertex
degrees. The goal of this paper is to devise efficient strategies to flip the
segments in order to obtain crossing-free segments after a small number of
flips. Linear and near-linear bounds on the number of flips were only known
for segments with endpoints in convex position. We generalize these results,
proving linear and near-linear bounds for cases with endpoints that are not in
convex position. Our results are proved in a general setting that applies to
multiple problems, using multigraphs and the distinction between removal and
insertion choices when performing a flip.

###### keywords:

Planar geometry, Reconfiguration, Matching, Euclidean TSP

##  1 Introduction

The _Euclidean Travelling Salesman Problem (TSP)_ is one of the most studied
geometric optimization problems. We are given a set $P$ of points in the plane
and the goal is to find a tour $S$ of minimum length. While the optimal
solution has no crossing segments, essentially all approximation algorithms,
heuristics, and PTASs may produce solutions $S$ with crossings. Given $S$, the
only procedure known to obtain a solution $S^{\prime}$ without crossings and
of shorter length is to perform a flip operation. In our case, a _flip_
consists of _removing_ a pair of crossing segments, and then _inserting_ a
pair of non-crossing segments preserving a tour (and consequently reducing its
length). Flips are performed in _sequence_ until a crossing-free tour is
obtained, in a procedure called _untangle_.

The same flip operation may be applied in other settings. More precisely, a
_flip_ consists of removing a pair of crossing segments $s_{1},s_{2}$ and
inserting a pair of segments $s^{\prime}_{1},s^{\prime}_{2}$ in a way that
$s_{1},s^{\prime}_{1},s_{2},s^{\prime}_{2}$ forms a cycle and a certain graph
_property_ is preserved. In the case of TSP tours, the property is being a
Hamiltonian cycle. Other properties have also been studied, such as spanning
trees, perfect matchings, and multigraphs. Notice that flips preserve the
degrees of all vertices and multiple copies of the same edge may appear when
we perform a flip on certain graphs.

When the goal is to obtain a crossing-free TSP tour, we are allowed to
_choose_ which pair of crossing segments to remove in order to perform fewer
flips, which we call _removal choice_ (Figure 1(a)). Notice that, in a tour,
choosing which pair of crossing edges we remove defines which pair of crossing
edges we insert. However, this is not the case for matchings and multigraphs.
There, we are also allowed to choose which pair of segments to insert among
two possibilities, which we call _insertion choice_ (Figure 1(b)).

.
(a) (b) .

Figure 1: (a) Three untangle sequences for a tour with different _removal
choices_. (b) Three untangle sequences for a matching with different
_insertion choices_. We highlight the segments removed and inserted at each
flip.

Using removal or insertion choices to obtain shorter flip sequences has not
been explicitly studied before and opens several new questions, while unifying
the solution to multiple reconfiguration problems. Next, we describe previous
work according to which choices are used. Throughout, $P$ denotes the set of
points and $n$ the number of segments.

Using no choice: Van Leeuwen et al. [27] showed that the _length_ (i.e. the
number of flips) of any untangle sequence for a TSP tour is
$\mathcal{O}(n^{3})$ and it is easy to construct $\Omega(n^{2})$ examples. The
same proof has been rediscovered in the context of matchings [9] after 35
years. If $P$ is in convex position, then the number of crossings decreases at
each flip, which gives a tight bound of $\Theta(n^{2})$. If all points except
the endpoints of $t$ segments are in convex position, then the authors [12]
recently showed a bound of $\mathcal{O}(tn^{2})$.

Using only insertion choice: Bonnet et al. [9] showed that using only
insertion choice, it is possible to untangle a matching using
$\mathcal{O}(n^{2})$ flips. Let $\sigma$ be the _spread_ of $P$, that is, the
ratio between the maximum and minimum distances among points in $P$. Using
insertion choice, it is also possible to untangle a matching using
$\mathcal{O}(n\sigma)$ flips [7].

Using only removal choice: If $P$ is in convex position, then by using
$\mathcal{O}(n)$ flips we can untangle a TSP tour [24, 29], as well as a red-
blue matching [7], while the best known bound for trees is $\mathcal{O}(n\log
n)$ [7]. If instead of convex position, we have colinear red points in a red-
blue matching, then $\mathcal{O}(n^{2})$ flips suffice [7, 13].

Using both removal and insertion choices: If $P$ is in convex position, then
by using $\mathcal{O}(n)$ flips we can untangle a matching [7].

###  1.1 New Results

Previous results are usually stated for a single graph property. Using
choices, we are able to state the results in a more general setting. Proofs
that use insertion choice are unlikely to generalize to red-blue matchings,
TSP tours, or trees, where insertion choice is not available (still, they may
hold for both non-bipartite matchings and multigraphs). In contrast, bounds
for multigraphs using only removal choice apply to all these cases.
Previously, we only knew linear or near-linear bounds when the points $P$ are
in convex position and removal choice is available. The goal of the paper is
to obtain linear and near-linear bounds to as many cases as possible,
considering near-convex configurations as well as removal and insertion
choices.

Let $P=C\cup T$ where $C$ is in convex position and the points of $T$ are
outside the convex hull of $C$, unless otherwise specified. Let $S$ be a
multiset of $n$ segments with endpoints $P$ and $t$ be the number of segments
with at least one endpoint in $T$. We prove the following results to untangle
$S$, and some are summarized in Table 1.

Using only insertion choice (Section 2): If $T=\emptyset$, then
$\mathcal{O}(n\log n)$ flips suffice. If $T$ is separated from $C$ by two
parallel lines, then $\mathcal{O}(tn\log n)$ flips suffice.

Using only removal choice (Section 3): If $|T|\leq 2$ and $t=\mathcal{O}(1)$,
then $\mathcal{O}(n\log n)$ flips suffice. In this case, our results hold with
the points $T$ being anywhere with respect to the convex hull of $C$. As the
bounds hold for trees, it is useful to compare them against the
$\mathcal{O}(n\log n)$ bound for trees from [7] that strongly uses the fact
that $S$ forms a tree. The $\mathcal{O}(\log n)$ factor is not present for the
special cases of TSP tours and red-blue matchings.

Using both removal and insertion choices (Section 4): If $T$ is separated from
$C$ by two parallel lines, then $\mathcal{O}(tn)$ flips suffice. If $T$ is
anywhere outside the convex hull of $C$ and $S$ is a matching, then
$\mathcal{O}(t^{3}n)$ flips suffice.

Table 1: Upper bounds to different versions of the problem with points having $\mathcal{O}(1)$ degree. The letter R corresponds to removal choice, I to insertion choice, and $\emptyset$ to no choice. New results are highlighted in yellow with the theorem number in parenthesis and tight bounds are bold. Property: | Matching | TSP, Red-Blue
---|---|---
Choices: | RI | I | R | $\emptyset$ | R | $\emptyset$
Convex |  $\mathbf{n}$ [7] |  yellow!50$n\log n$ (2.1) |  yellow!50$n\log n$ (3.1) | $\mathbf{n^{2}}$ |  $\mathbf{n}$ [7, 24, 29] | $\mathbf{n^{2}}$
$|T|=1$ |  yellow!50$\mathbf{n}$ (4.1) |  yellow!50$n\log n$ (2.3) |  yellow!50$n\log n$ (3.5) |  $\mathbf{n^{2}}$ [12] |  yellow!50$\mathbf{n}$ (3.5) |  $\mathbf{n^{2}}$ [12]
$|T|=2$ |  yellow!50$\mathbf{n}$ (4.5) |  $n^{2}$ [9] |  yellow!50$n\log n$ (3.7) |  $\mathbf{n^{2}}$ [12] |  yellow!50$\mathbf{n}$ (3.7) |  $\mathbf{n^{2}}$ [12]
separated |  yellow!50$tn$ (4.1) |  yellow!50$tn\log n$ (2.3) |  $tn^{2}$ [12]
$C\cup T$ |  yellow!50$t^{3}n$ (4.5) |  $n^{2}$ [9] |  $tn^{2}$ [12]

In a matching or TSP tour, we have $t=\mathcal{O}(|T|)$ and
$n=\mathcal{O}(|P|)$, however in a tree, $t$ can be as high as
$\mathcal{O}(|T|^{2})$. In a multigraph $t$ and $n$ can be much larger than
$|T|$ and $|P|$. The theorems describe more precise bounds as functions of all
these parameters. For simplicity, the introduction only shows bounds in terms
of only $n$ and $t$.

###  1.2 Related Reconfiguration Problems

Combinatorial reconfiguration studies the step-by-step transition from one
solution to another, for a given combinatorial problem. Many reconfiguration
problems are presented in [26]. We give a brief overlook of reconfiguration
among line segments using alternative flip operations.

The _2OPT flip_ is not restricted to crossing segments. It removes and inserts
pairs of segments (the four segments forming a cycle) as the total length
decreases. In contrast to flips among crossing segments, the number of 2OPT
flips performed may be exponential [14].

It is possible to relax the flip definition even further to all operations
that replace two segments by two others forming a cycle [5, 6, 8, 10, 15, 28].
This definition has also been considered for multigraphs [17, 18, 20].

Another type of flip consists of removing a single segment and inserting
another one. Such flips are widely studied for triangulations [3, 19, 21, 22,
23, 25]. They have also been considered for non-crossing trees [1] and paths.
It is possible to reconfigure any two non-crossing paths if the points are in
convex position [4, 11] or if there is _one_ point inside the convex hull [2].

###  1.3 Preliminaries

Throughout, we consider _multigraphs_ $(P,S)$ whose vertices $P$ (called
_endpoints_) are points in the plane and edges $S$ are a multiset of line
_segments_. We assume that the endpoints are in _general position_ and that
the two endpoints of a segment are distinct. Given two (possibly equal) sets
$P_{1},P_{2}$ of endpoints, we say that a segment is a _$P_{1}P_{2}$ -segment_
if one endpoint is in $P_{1}$ and the other is in $P_{2}$. Similarly, we say
that a segment is a _$P_{1}$ -segment_ if at least one endpoint is in $P_{1}$.

We say that two segments _cross_ if they intersect at a single point that is
not an endpoint of either segment. We say that a line _crosses_ a segment if
they intersect at a single point that is not an endpoint of the segment. We
say that a segment or a line $h$ _separates_ a set of points $P$ if $P$ can be
partitioned into two non-empty sets $P_{1},P_{2}$ such that every segment
$p_{1}p_{2}$ with $p_{1}\in P_{1},p_{2}\in P_{2}$ crosses $h$. Given a set of
segments $S$, the _line potential_ $\lambda(\ell)$ is the number of segments
of $S$ crossed by $\ell$. Several proofs in this paper use the following two
lemmas from previous papers.

######  Lemma 1.1 ([27]).

Given a multiset $S$ of segments and a line $\ell$, let $\lambda(\ell)$ be the
number of segments in $S$ crossing $\ell$. Then, $\lambda(\ell)$ never
increases at a flip.

######  Lemma 1.2 ([9]).

Consider a partition $S=\bigcup_{i}S_{i}$ of the multiset $S$ of segments and
let $P_{i}$ be the set of endpoints of $S_{i}$. If no segment of
$\binom{P_{i}}{2}$ crosses a segment of $\binom{P_{j}}{2}$ for $i\neq j$, then
the sequences of flips in each $S_{i}$ are independent.

We say that a segment $s$ is _uncrossable_ if for any two endpoints
$p_{1},p_{2}$, we have that $p_{1}p_{2}$ do not cross $s$. Lemma 1.2 implies
that an uncrossable segment cannot be flipped.

Our bounds often have terms like $\mathcal{O}(tn)$ and $\mathcal{O}(n\log|C|)$
that would incorrectly become $0$ if $t$ or $\log|C|$ is $0$. In order to
avoid this problem, factors in the $\mathcal{O}$ notation should be made at
least 1. For example, the aforementioned bounds should be respectively
interpreted as $\mathcal{O}((1+t)n)$ and $\mathcal{O}(n\log(2+|C|))$.

###  1.4 Techniques

To prove our results, we combine previous and new _potential functions_ with
refined strategies and analysis. Van Leeuwen et al. [27] as well as Bonnet et
al. [9] consider $\lambda(\ell)$ for a set $L$ of all $\mathcal{O}(|P|^{2})$
lines defined by $P$. Since there always exists a line in $L$ whose potential
decreases at a flip, we obtain the $\mathcal{O}(|P|^{2}n)=\mathcal{O}(n^{3})$
classical bound without any choice. Bonnet et al. [9] show that a set $L$ of
$|P|-1$ parallel lines (with one point between two consecutive lines) suffices
with insertion choice. Since there is always an insertion choice that makes
some $\lambda(\ell)$ decrease for $\ell\in L$, the
$\mathcal{O}(|P|n)=\mathcal{O}(n^{2})$ bound follows.

In order to avoid a quadratic dependency in $n$, new line potentials have to
be introduced with careful removal and/or insertion choices. For example, to
prove Theorem 4.5, we have to perform several flips in order to find a line
$\ell$ with $\lambda(\ell)=\mathcal{O}(t)$ before applying the line potential
argument. In contrast, to prove Theorem 2.3, we modify the line potential to
only count the $t$ $T$-segments. However, with this change the line potential
may increase, which we need to handle properly.

Another key potential, inspired by [7] and used for the convex case is the
_depth potential_ $\delta(p_{a}p_{b})$ of a segment $p_{a}p_{b}$, defined as
the number of points between $p_{a}$ and $p_{b}$ along the convex hull
boundary with a given orientation. Careful removal and insertion choices as
well as adaptations of this potential had to be made in order to guarantee
that the potential decreases during most flips and never increases by too
much. For example, to prove Theorems 2.1 and 2.3, we had to consider the
product of the depth, instead of the usual sum. To prove Theorem 3.1, we had
to modify the depth potential to only count endpoints of segments that have
crossings, which we call the _crossing depth_ $\delta_{\times}(p_{a}p_{b})$.

In the convex case, the number of crossings decreases at each flip, which
implies the trivial $\binom{n}{2}$ upper bound. However, the number of
crossings may increase when the points are not in convex position. An analysis
of the number of crossings is used to bound the number of flips in the proof
of Theorem 3.9.

Finally, we use the concept of _splitting_ from [9], presented in Lemma 1.2.
The difficulty of splitting is to obtain the disjoint sets required by the
lemma. For example, in Theorem 4.5, we untangle segments with both endpoints
in $C$ last to obtain the desired separation. In Theorem 3.7, we carefully
find lines that split the original problem into problems with a smaller value
of $t$ that are solved recursively. The special case of uncrossable segments
is used in Theorems 3.5 and 3.7.

##  2 Insertion Choice

In this section, we show how to untangle a multigraph using only insertion
choice, that is, our strategies do not choose which pair of crossing segments
is removed, but only which pair of segments with the same endpoints is
subsequently inserted. We start with the convex case, followed by points
outside the convex separated by two parallel lines.

###  2.1 Convex

Let $P=C=\\{p_{1},\ldots,p_{|C|}\\}$ be a set of points in convex position
sorted in counterclockwise order along the convex hull boundary (Figure 2(a)).
Given a segment $p_{a}p_{b}$, we define the _depth_
$\delta(p_{a}p_{b})=|b-a|$. This definition resembles but is not the same as
the depth used in [7]. We use the depth to prove the following theorem.

.
(a) (b) (c) .

Figure 2: (a) A multigraph $(C,S)$ with $|C|=14$ points in convex position and
$n=9$ segments. (b) Insertion choice for Case 1 and 2 of the proof of Theorem
2.1. (c) Insertion choice for Case 3.

######  Theorem 2.1.

Every multigraph $(C,S)$ with $C$ in convex position has an untangle sequence
of length $\mathcal{O}(n\log|C|)=\mathcal{O}(n\log n)$ using only insertion
choice, where $n=|S|$.

######  Proof 2.2.

Let the potential function

$\phi(S)=\prod_{s\in S}\delta(s).$

As $\delta(s)\in\\{1,\ldots,|C|-1\\}$, we have that $\phi(S)$ is integer,
positive, and at most $|C|^{n}$. Next, we show that for any flipped pair of
segments $p_{a}p_{b},p_{c}p_{d}$ there exists an insertion choice that
multiplies $\phi(S)$ by a factor of at most $3/4$, and the theorem follows.

Consider a flip of a segment $p_{a}p_{b}$ with a segment $p_{c}p_{d}$ and
assume without loss of generality that $a<c<b<d$. The contribution of the pair
of segments $p_{a}p_{b},p_{c}p_{d}$ to the potential $\phi(S)$ is the factor
$f=\delta(p_{a}p_{b})\delta(p_{c}p_{d})$. Let $f^{\prime}$ be the factor
corresponding to the pair of inserted segments.

Case 1: If $\delta(p_{a}p_{c})\leq\delta(p_{c}p_{b})$, then we insert the
segments $p_{a}p_{c}$ and $p_{b}p_{d}$ and we get
$f^{\prime}=\delta(p_{a}p_{c})\delta(p_{b}p_{d})$ (Figure 2(b)). We notice
$\delta(p_{a}p_{b})=\delta(p_{a}p_{c})+\delta(p_{c}p_{b})$. It follows
$\delta(p_{a}p_{c})\leq\delta(p_{a}p_{b})/2$ and we have
$\delta(p_{b}p_{d})\leq\delta(p_{c}p_{d})$ and then $f^{\prime}\leq f/2$.

Case 2: If $\delta(p_{b}p_{d})\leq\delta(p_{c}p_{b})$, then we insert the same
segments $p_{a}p_{c}$ and $p_{b}p_{d}$ as previously. We have
$\delta(p_{a}p_{c})\leq\delta(p_{a}p_{b})$ and
$\delta(p_{b}p_{d})\leq\delta(p_{c}p_{d})/2$, which gives $f^{\prime}\leq
f/2$.

Case 3: If (i) $\delta(p_{a}p_{c})>\delta(p_{c}p_{b})$ and (ii)
$\delta(p_{b}p_{d})>\delta(p_{c}p_{b})$, then we insert the segments
$p_{a}p_{d}$ and $p_{c}p_{b}$ (Figure 2(c)). The contribution of the new pair
of segments is $f^{\prime}=\delta(p_{a}p_{d})\delta(p_{c}p_{b})$. We introduce
the coefficients $x=\frac{\delta(p_{a}p_{c})}{\delta(p_{c}p_{b})}$ and
$y=\frac{\delta(p_{b}p_{d})}{\delta(p_{c}p_{b})}$ so that
$\delta(p_{a}p_{c})=x\delta(p_{c}p_{b})$ and
$\delta(p_{b}p_{d})=y\delta(p_{c}p_{b})$. It follows that
$\delta(p_{a}p_{b})=(1+x)\delta(p_{c}p_{b})$,
$\delta(p_{c}p_{d})=(1+y)\delta(p_{c}p_{b})$ and
$\delta(p_{a}p_{d})=(1+x+y)\delta(p_{c}p_{b})$. The ratio $f^{\prime}/f$ is
equal to a function $g(x,y)=\frac{1+x+y}{(1+x)(1+y)}$. Due to (i) and (ii), we
have that $x\geq 1$ and $y\geq 1$. In other words, we can upper bound the
ratio $f^{\prime}/f$ by the maximum of the function $g(x,y)$ with $x,y\geq 1$.
It is easy to show that the function $g(x,y)$ is decreasing with both $x$ and
$y$. Then its maximum is obtained for $x=y=1$ and it is equal to $3/4$,
showing that $f^{\prime}\leq 3f/4$.

###  2.2 Separated by Two Parallel Lines

In this section, we prove the following theorem, which is a generalization of
Theorem 2.1.

.
(a) (b) .

Figure 3: (a) Statement of Theorem 2.3. (b) Some insertion choices in the
proof of Theorem 2.3.

######  Theorem 2.3.

Consider a multigraph $(P,S)$ with $P=C\cup T_{1}\cup T_{2}$ where $C$ is in
convex position and there exist two horizontal lines $\ell_{1},\ell_{2}$, with
$T_{1}$ above $\ell_{1}$ above $C$ above $\ell_{2}$ above $T_{2}$. Let
$T=T_{1}\cup T_{2}$, $n=|S|$, and $t$ be the number of $T$-segments. There
exists an untangle sequence of length
$\mathcal{O}(t|P|\log|C|+n\log|C|)=\mathcal{O}(tn\log n)$ using only insertion
choice.

######  Proof 2.4.

We start by describing the insertion choice for flips involving at least one
point in $T$. Let $p_{1},\ldots,p_{|P|}$ be the points $P$ sorted vertically
from top to bottom. Consider a flip involving the points
$p_{a},p_{b},p_{c},p_{d}$ with $a<b<c<d$. The insertion choice is to create
the segments $p_{a}p_{b}$ and $p_{c}p_{d}$. See Figure 3(b). As in [9], we
define the potential $\eta$ of a segment $p_{i}p_{j}$ as

$\eta(p_{i}p_{j})=|i-j|.$

Notice that $\eta$ is an integer between $1$ and $|P|-1$. We define
$\eta_{T}(S)$ as the sum of $\eta(p_{i}p_{j})$ for $p_{i}p_{j}\in S$ with
$p_{i}$ or $p_{j}$ in $T$. Notice that $0<\eta_{T}(S)<t|P|$. It is easy to
verify that any flip involving a point in $T$ decreases $\eta_{T}(S)$ and
other flips do not change $\eta_{T}(S)$. Hence, the number of flips involving
at least one point in $T$ is $\mathcal{O}(t|P|)$.

For the flips involving only points of $C$, we use the same choice as in the
proof of Theorem 2.1. The potential function

$\phi(S)=\prod_{p_{i}p_{j}\in S\;:\;p_{i}\in C\text{ and }p_{j}\in
C}\delta(p_{i}p_{j})$

is at most $|C|^{n}$ and decreases by a factor of at most $3/4$ at every flip
that involves only points of $C$.

However, $\phi(S)$ may increase by a factor of $\mathcal{O}(|C|^{2})$ when
performing a flip that involves a point in $T$. As such flips only happen
$\mathcal{O}(t|P|)$ times, the total increase is at most a factor of
$|C|^{\mathcal{O}(t|P|)}$.

Concluding, the number of flips involving only points in $C$ is at most

$\log_{4/3}\left(|C|^{\mathcal{O}(n)}|C|^{\mathcal{O}(t|P|)}\right)=\mathcal{O}(n\log|C|+t|P|\log|C|).$

##  3 Removal Choice

In this section, we show how to untangle a multigraph using only removal
choice. We start with the convex case, followed by $1$ point inside or outside
the convex, then $2$ points outside the convex, $2$ points inside the convex,
and $1$ point inside and $1$ outside the convex. As only removal choice is
used, all results also apply to red-blue matchings, TSP tours, and trees.

###  3.1 Convex

Let $P=C=\\{p_{1},\ldots,p_{|C|}\\}$ be a set of points in convex position
sorted in counterclockwise order along the convex hull boundary and consider a
set of segments $S$ with endpoints $P$. Given a segment $p_{a}p_{b}$ and
assuming without loss of generality that $a<b$, we define the _crossing depth_
$\delta_{\times}(p_{a}p_{b})$ as the number of points in
$p_{a+1},\ldots,p_{b-1}$ that are an endpoint of a segment in $S$ that crosses
any other segment in $S$ (not necessarily $p_{a}p_{b}$). We use the crossing
depth to prove the following theorem, which implies a simpler and more general
proof of the $\mathcal{O}(n\log n)$ bound for trees [7].

.
(a) (b) (c) .

Figure 4: Proof of Theorem 3.1. (a) The segments of a convex multigraph are
labeled with the crossing depth. (b,c) Two possible pairs of inserted
segments, with one segment of the pair having crossing depth
$\lfloor\frac{3}{2}\rfloor=1$.

######  Theorem 3.1.

Every multigraph $(C,S)$ with $C$ in convex position has an untangle sequence
of length $\mathcal{O}(n\log|C|)=\mathcal{O}(n\log n)$ using only removal
choice, where $n=|S|$.

######  Proof 3.2.

We repeat the following procedure until there are no more crossings. Let
$p_{a}p_{b}\in S$ be a segment _with crossings_ (hence, crossing depth at
least one) and $a<b$ minimizing $\delta_{\times}(p_{a}p_{b})$ (Figure 4(a)).
Let $q_{1},\ldots,q_{\delta_{\times}(p_{a}p_{b})}$ be the points defining
$\delta_{\times}(p_{a}p_{b})$ in order and let
$i=\lceil\delta_{\times}(p_{a}p_{b})/2\rceil$. Since $p_{a}p_{b}$ has minimum
crossing depth, the point $q_{i}$ is the endpoint of segment $q_{i}p_{c}$ that
crosses $p_{a}p_{b}$. When flipping $q_{i}p_{c}$ and $p_{a}p_{b}$, we obtain a
segment $s$ (either $s=q_{i}p_{a}$ or $s=q_{i}p_{b}$) with
$\delta_{\times}(s)$ at most half of the original value of
$\delta_{\times}(p_{a}p_{b})$ (Figure 4(b,c)). Hence, this operation always
divides the value of the smallest positive crossing depth by at least two. As
the crossing depth is an integer smaller than $|C|$, after performing this
operation $\mathcal{O}(\log|C|)$ times, it produces a segment of crossing
depth $0$. As the segments of crossing depth $0$ can no longer participate in
a flip, the claimed bound follows.

###  3.2 One Point Inside or Outside a Convex

In this section, we prove Theorem 3.5. In the case of TSP tours [24, 29] and
red-blue matchings [8], the preprocessing to untangle $CC$-segments takes
$\mathcal{O}(n)$ flips. However, in the case of trees [8] and in general
(Theorem 3.1), the best bound known is $\mathcal{O}(n\log n)$. We first state
a lemma used to prove Theorem 3.5.

######  Lemma 3.3.

Consider a set $C$ of points in convex position, and a multiset $S$ of $n$
crossing-free segments with endpoints in $C$. Consider the multiset
$S\cup\\{s\\}$ where $s$ is an extra segment with one endpoint in $C$ and one
endpoint $q$ anywhere in the plane. There exists an untangle sequence for
$S\cup\\{s\\}$ of length $\mathcal{O}(n)$ using only removal choice.

######  Proof 3.4.

Iteratively flip the segment $qp_{1}$ with the segment $p_{2}p_{3}\in S$
crossing $qp_{1}$ the farthest from $q$. This flip inserts a $CC$-segment
$p_{1}p_{2}$, which is impossible to flip again, because the line $p_{1}p_{2}$
is crossing free. The flip does not create any crossing between $CC$-segments.

We are now ready to state and prove the theorem.

######  Theorem 3.5.

Consider a multigraph $(P,S)$ with $P=C\cup T$ where $C$ is in convex
position, and $T=\\{q\\}$, and such that there is no crossing pair of
$CC$-segments (possibly after a preprocessing for the convex case). Let
$n=|S|$ and $t$ be the number of $T$-segments. There exists an untangle
sequence of length $\mathcal{O}(tn)$ using only removal choice.

######  Proof 3.6.

For each segment $s$ with endpoint $q$ with crossing, we apply Lemma 3.3 to
$s$ and the $CC$-segments crossing $s$. Once a segment $s$ incident to $q$ is
crossing free, it is impossible to flip it again as we fall in one of the
following cases. Let $\ell$ be the line containing $s$.

Case 1: If $\ell$ is crossing free, then it splits the multigraph in three
partitions: the segments on one side of $\ell$, the segments on the other side
of $\ell$, and the segment $s$ itself.

Case 2: If $\ell$ is not crossing free and $q$ is outside the convex hull of
$C$, then $s$ is _uncrossable_.

Case 3: If $q$ is inside the convex hull of $C$, then introducing a crossing
on $s$ would require that $q$ lies in the interior of the convex quadrilateral
whose diagonals are the two segments removed by a flip. The procedure excludes
this possibility by ensuring that there are no crossing pair of $CC$-segments,
and, therefore, that one of the removed segment already has $q$ as an
endpoint.

Therefore, we need at most $n$ flips for each of the $t$ segments incident to
$q$.

###  3.3 Two Points Outside a Convex

In this section, we prove a theorem with a bound that is exponential in $t$,
which makes it of little interest for large $t$. Notice, however, that in
matchings $t\leq 2$, in a TSP tour $t\leq 4$, and in a binary tree $t\leq 6$.
Also notice that the definition of $t$ is different from other theorems (here
$TT$-segments are counted twice). Both definitions are equivalent up to a
factor of $2$, but since $t$ appears in the exponent, they are not
exchangeable.

######  Theorem 3.7.

Consider a multigraph $(P,S)$ with $P=C\cup T$ where $C$ is in convex
position, the points of $T$ are outside the convex hull of $C$, and $|T|\leq
2$. Let $n=|S|$ and $t$ be the sum of the degrees of the points in $T$. There
exists an untangle sequence of length $\mathcal{O}(2^{t}d_{\text{conv}}(n))$
using only removal choice, where $d_{\text{conv}}(n)$ is the number of flips
to untangle any multiset of at most $n$ segments with endpoints in convex
position.

######  Proof 3.8.

Throughout this proof, we partition the $TT$-segments respectively the
$CT$-segments into two types: _$TTI$ -segment_ and _$CTI$ -segment_ if it
intersects the interior of the convex hull of $C$ and _$TTO$ -segment_ and
_$CTO$ -segment_ otherwise. Let $f(t)$ be the number of flips to untangle a
multiset $S$ as in the statement of the theorem. The proof proceeds by
induction. The base case is $t=0$, when $f(0)\leq d_{\text{conv}}(n)$ by
definition of $d_{\text{conv}}(n)$.

Next, we show how to bound $f(t)$ for $t>0$, but first we need some
definitions. A line $\ell$ is a _$T$ -splitter_ if $\ell$ is crossing free and
either $\ell$ contains a $T$-segment or there are $T$-segments on both sides
of $\ell$. We abusively say that a segment $s$ is a $T$-splitter if the line
containing $s$ is a $T$-splitter. A $T$-splitter is useful because we can
apply Lemma 1.2 and solve sub-problems with a lower value of $t$ by induction.

Phase 1: untangle all but one segment by induction. We remove an arbitrary
$CT$-segment or $TT$-segment $s$ from $S$. We then use induction to untangle
$S$ using $f(t-1)$ flips and insert the segment $s$ back in $S$ afterwards.
Notice that all crossings are now on $s$.

Phase 2.1: apply induction if possible. If $S$ admits a $T$-splitter $\ell$,
then we apply Lemma 1.2 to solve each side of $\ell$ independently using
induction.

If $S$ has a crossing-free $TTO$-segment $qq^{\prime}$ such that the line
$qq^{\prime}$ is not crossing free, then $qq^{\prime}$ is uncrossable, and we
remove $qq^{\prime}$ from $S$ and untangle $S$ by induction. Similarly, in the
case where $T=\\{q,q^{\prime}\\}$ and where $qq^{\prime}$ is a $TTI$-segment,
if $S$ has a $CTO$-segment, say $pq$, then $pq$ is uncrossable, and we remove
$pq$ from $S$ and untangle $S$ by induction.

In all the three cases of Phase 2.1 we get $f(t)\leq
f(t-1)+f(t_{1})+f(t_{2})$, where $t_{1}+t_{2}\leq t$ and $t_{1},t_{2}\geq 1$.

Phase 2.2: split after one flip. If $S$ contains no $T$-splitter and if $s$ is
a $TT$-segment, then there remains no $CT$-segment in $S$ (as every
$CT$-segment shares an endpoint with the $TT$-segment $s$ that contains all
crossings), and $s$ crosses a $CC$-segment $s^{\prime}$. A crossing-free
$CT$-segment would either be a $CTI$-segment, hence a $T$-splitter, or a
$CTO$-segment and, hence uncrossable and removed by one of the induction cases
of Phase 2.1.

The segment $s^{\prime}$ becomes a $T$-splitter after flipping $s$ with
$s^{\prime}$, and we invoke induction. By Lemma 1.2, we get in this case
$f(t)\leq f(t-1)+1+f(t_{1})+f(t_{2})$, where $t_{1}+t_{2}\leq t$ and
$t_{1},t_{2}\geq 1$.

Phase 2.3: split after $\mathcal{O}(n)$ flips. In this case, $S$ contains no
$T$-splitter and $s$ is a $CT$-segment, say with $q$ as its endpoint in $T$.
While $s^{\prime}$, the segment of $S$ that crosses $s$ the farthest away from
$q$, is a $CC$-segment, we flip $s$ and $s^{\prime}$ and we set $s$ to be the
newly inserted $CT$-segment incident to $q$. By Lemma 3.3, at most $n$ flips
are performed in this loop.

At the end of the loop, either $s$ is crossing free, or $s^{\prime}$ is a
$CT$-segment, say with $q^{\prime}$ as its endpoint in $T$. Then, we also flip
$s$ and $s^{\prime}$.

Insertion case 1: If two $CT$-segments are inserted, then, either one of them
is uncrossable (this is the case if $s^{\prime}$ is a $CTO$-segment), or
$s^{\prime}$ is now a $T$-splitter (recall that if $qq^{\prime}$ is a
$TTI$-segment, then all the $CTO$-segments have been removed at Phase 2.1.).

Insertion case 2: If the $TT$-segment $qq^{\prime}$ is inserted, then the
inserted $CC$-segment is crossing free (as in the proof of Lemma 3.3), and, if
$qq^{\prime}$ is not already crossing free, we flip $qq^{\prime}$ with any
segment, say $pp^{\prime}$.

Next, we split $S$ as follows. Among the $CTI$-segments of $S$ which are on
the upper (respectively lower) side of the line $qq^{\prime}$, consider the
one whose endpoint $p_{\text{upper}}$ (respectively $p_{\text{lower}}$) in $C$
is the closest to the line $qq^{\prime}$. The segments of $S$ are either
inside or outside the convex quadrilateral
$qp_{\text{lower}}q^{\prime}p_{\text{upper}}$, and we know that only the
segments inside may have crossings. By Lemma 1.2, we remove from $S$ all the
segments outside $qp_{\text{lower}}q^{\prime}p_{\text{upper}}$. Recall that,
in our case, $qq^{\prime}$ is a $TTI$-segment, and all the $CTO$-segments have
been removed at Phase 2.1. The line $pp^{\prime}$ is finally a $T$-splitter.
Again, by Lemma 1.2, we get in this case $f(t)\leq
f(t-1)+n+2+f(t_{1})+f(t_{2})$, where $t_{1}+t_{2}\leq t$ and $t_{1},t_{2}\geq
1$.

The last bound on $f(t)$ dominates the recurrence. Using that
$f(t_{1})+f(t_{2})\leq f(t-1)+f(1)$ and $t<n$ we get

$f(t)\leq f(t-1)+n+2+f(t_{1})+f(t_{2})\leq\mathcal{O}(n)+2f(t-1),$

which solves to $f(t)=\mathcal{O}(2^{t}d_{\text{conv}}(n))$ as claimed.

###  3.4 Two Points inside a Convex

We prove a similar theorem for two points inside the convex hull of $C$.

######  Theorem 3.9.

Consider a multigraph $(P,S)$ with $P=C\cup T$ where $C$ is in convex
position, the points of $T$ are inside the convex hull of $C$, and
$T=\\{q,q^{\prime}\\}$. Let $n=|S|$ and $t$ be the number of $T$-segments.
There exists an untangle sequence of length
$\mathcal{O}(d_{\text{conv}}(n)+tn)$ using only removal choice, where
$d_{\text{conv}}(n)$ is the number of flips to untangle any multiset of at
most $n$ segments with endpoints in convex position.

######  Proof 3.10.

The untangle sequence is decomposed in five phases. At the end of each phase,
a new type of crossings is removed, and types of crossings removed in the
previous phases are not present, even if they may temporarily appear during
the phase.

Phase 1 ($\mathbf{CT\times CT}$). In this phase, we remove all crossings
between pairs of $CT$-segments using
$\mathcal{O}(d_{\text{conv}}(t))=\mathcal{O}(d_{\text{conv}}(n))$ flips. We
separately solve two convex sub-problems defined by the $CT$-segments, one on
each side of the line $qq^{\prime}$.

Phase 2 ($\mathbf{CC\times CC}$). In this phase, we remove all crossings
between pairs of $CC$-segments using $\mathcal{O}(d_{\text{conv}}(n))$ flips.
As no $CT$-segment has been created, there is still no crossing between a pair
of $CT$ segments. Throughout, our removal will preserve the invariant that no
pair of $CC$-segments crosses.

Phase 3 ($\mathbf{CT\times\textbf{non-central }CC}$). We distinguish between a
few types of $CC$-segments. The central $CC$-segments cross the segment
$qq^{\prime}$ (regardless of $qq^{\prime}$ being in $S$ or not), while the
_non-central_ do not. The peripheral $CC$-segments cross the line
$qq^{\prime}$ but not the segment $qq^{\prime}$, while the _outermost_
$CC$-segments do not cross either. In this phase, we remove all crossings
between $CT$-segments and non-central $CC$-segments.

Given a non-central $CC$-segment $pp^{\prime}$, let the _out-depth_
$\delta^{\prime}(pp^{\prime})$ be the number of points of $C$ that are
contained inside the halfplane bounded by the line $pp^{\prime}$ and not
containing $T$. Also, let $\chi$ be the number of crossings between the non-
central $CC$-segments and the $CT$-segments. At the end of each step the two
following invariants are preserved. (i) No pair of $CC$-segments crosses. (ii)
No pair of $CT$-segments crosses.

At each step, we choose to flip the non-central $CC$-segment $pp^{\prime}$ of
minimum out-depth that crosses a $CT$-segment. We flip $pp^{\prime}$ with the
$CT$-segment $q^{\prime\prime}p^{\prime\prime}$ (with
$q^{\prime\prime}\in\\{q,q^{\prime}\\}$) that crosses $pp^{\prime}$ at the
point closest to $p$ (Figure 5(a) and Figure 6(a)). One of the possibly
inserted pairs may contain a $CT$-segment $s$ that crosses another
$CT$-segment $s^{\prime}$, violating the invariant (ii) (Figure 5(b) and
Figure 6(b)). If there are multiple such segments $s^{\prime}$, then we
consider $s^{\prime}$ to be the segment whose crossing with $s$ is closer to
$q^{\prime\prime}$. We flip $s$ and $s^{\prime}$ and obtain either two
$CT$-segments (Figure 5(c) and Figure 6(c)) or a $CC$-segment and the segment
$qq^{\prime}$ (Figure 5(d) and Figure 6(d)). The analysis is divided in two
main cases.

. .
. (a) (b) (c) (d) .

Figure 5: Theorem 3.9, Phase 3 when $pp^{\prime}$ is an outermost segment.

If $pp^{\prime}$ is an outermost $CC$-segment (see Figure 5), then case
analysis shows that the two invariants are preserved and $\chi$ decreases.

. .
. (a) (b) (c) (d) .

Figure 6: Theorem 3.9, Phase 3 when $pp^{\prime}$ is a peripheral segment.

If $pp^{\prime}$ is a peripheral $CC$-segment (see Figure 6), then a case
analysis shows that the two invariants are preserved and $\chi$ has the
following behavior. If no $CC$-segment is inserted, then $\chi$ decreases.
Otherwise a $CC$-segment and a $TT$-segment are inserted and $\chi$ may
increase by $\mathcal{O}(t)$ (Figure 6(d)). Notice that the number of times
the $TT$-segment $qq^{\prime}$ is inserted is $\mathcal{O}(t)$, which bounds
the total increase by $\mathcal{O}(t^{2})$.

As $\chi=\mathcal{O}(tn)$, the total increase is $\mathcal{O}(t^{2})$, and
$\chi$ decreases at all but $\mathcal{O}(t)$ steps, we have that the number of
flips in Phase 3 is $\mathcal{O}(tn)$.

Phase 4 ($\mathbf{CT\times\textbf{central }CC}$). At this point, each crossing
involves a central $CC$-segment and either a $CT$-segment or the $TT$-segment
$qq^{\prime}$. In this phase, we remove all crossings between $CT$-segments
and central $CC$-segments, ignoring the $TT$-segments. This phase ends with
crossings only between $qq^{\prime}$ and central $CC$-segments.

. .
. (a) (b) (c) (d) .

Figure 7: Theorem 3.9, Phase 4. (a) A pair of $CT$-segments with an ear. (b) A
$CC$-segment and a $CT$-segment with an ear. (c) Flipping an ear that produces
crossing pairs of $CT$-segments. (d) Flipping an ear that inserts a non-
central $CC$-segment with crossings.

Given four endpoints $q^{\prime\prime}\in T$, $p,p^{\prime\prime}\in C$, and
$x\in C\cup T$, we say that a pair of segments
$p^{\prime\prime}q^{\prime\prime},xp\in S$ crossing at a point $c$ contains an
_ear_ $\widehat{pp^{\prime\prime}}$ if the interior of the triangle
$pp^{\prime\prime}c$ intersects no segment of $S$ (see Figure 7(a) and 7(b)).
Every set of segments with endpoints in $C\cup T$ with $|T|=2$ that has
crossings (not involving the $TT$-segment) contains an ear (adjacent to the
crossing that is farthest from the line $qq^{\prime}$).

At each _step_ , we flip a pair of segments
$p^{\prime\prime}q^{\prime\prime},xp$ that contains an ear
$\widehat{pp^{\prime\prime}}$, prioritizing pairs where both segments are
$CT$-segments. Notice that, even though initially we did not have crossing
pairs of $CT$-segments, they may be produced in the flip (Figure 7(c)). If the
flip inserts a non-central $CC$-segment which crosses some $CT$-segments
(Figure 7(d)), then, we perform the following _while loop_. Assume without
loss of generality that $qq^{\prime}$ is horizontal and $s$ is closer to
$q^{\prime}$ than to $q$. While there exists a non-central $CC$-segment $s$
with crossings, we flip $s$ with the $CT$-segment $s^{\prime}$ crossing $s$
that comes first according to the following order. As a first criterion, a
segment incident to $q$ comes before a segment incident to $q^{\prime}$. As a
second tie-breaking criterion, a segment whose crossing point with $s$ that is
farther from the line $qq^{\prime}$ comes before one that is closer.

Let $\chi=\mathcal{O}(tn)$ be the number of crossings between central
$CC$-segments and $CT$-segments plus the number of crossings between
$CT$-segments. A case analysis shows that the value of $\chi$ decreases at
each step. If no non-central $CC$-segment is inserted, then the corresponding
step consists of a single flip. As $\chi$ decreases, there are
$\mathcal{O}(tn)$ steps that do not insert a non-central $CC$-segment.

However, if a non-central $CC$-segment is inserted, at the end of the step we
inserted a $CC$-segment that can no longer be flipped (Lemma 1.2). As the
number of $CC$-segments is $\mathcal{O}(n)$, we have that the number of times
the while loop is executed is $\mathcal{O}(n)$. Since each execution of the
while loop performs $\mathcal{O}(t)$ flips, we have a total of
$\mathcal{O}(tn)$ flips in this phase.

Phase 5 ($\mathbf{TT\times\textbf{central }CC}$). In this phase, we remove all
crossings left, which are between the possibly multiple copies of the
$TT$-segment $qq^{\prime}$ and central $CC$-segments. The endpoints of the
segments with crossings are in convex position and all other endpoints are
outside their convex hull. Hence, by Lemma 1.2, it is possible to obtain a
crossing-free multigraph using $\mathcal{O}(d_{\text{conv}}(n))$ flips.

###  3.5 One Point inside and One Point Outside a Convex

Given an endpoint $p$, let $\delta(p)$ denote the degree of $p$, that is, the
number of segments incident to $p$. The following lemma is used to prove
Theorem 3.13.

######  Lemma 3.11.

Consider a multigraph $(P,S)$ with $P=C\cup T$ where $C$ is in convex
position, and $T=\\{q,q^{\prime}\\}$ such that $q$ is outside the convex hull
of $C$ and $q^{\prime}$ is inside the convex hull of $C$. Consider that $q$ is
the endpoint of a single segment $s$ and all crossings are on $s$. Let $n=|S|$
and $t=\mathcal{O}(\delta(q^{\prime}))$ be the number of $T$-segments. There
exists a flip sequence of length $\mathcal{O}(tn)$ using only removal choice
that ends with all crossings (if any) on the segment $qq^{\prime}$.

######  Proof 3.12.

We proceed as follows, while $s$ has crossings. For induction purpose, let
$f(n^{\prime})$ be the length of the flip sequence in the lemma statement for
$n^{\prime}<n$ segments.

Let $s^{\prime}$ be the segment that crosses $s$ at the point farthest from
$q$. We flip $s$ and $s^{\prime}$, arriving at one of the three cases below
(Figure 8).

Case 1 Case 2 Case 3

Figure 8: The three cases in the proof of Lemma 3.11.

Case 1 ($\mathbf{CT\times CC)}$. In this case, the segment $s^{\prime}$ is a
$CC$-segment. Notice that the line $\ell$ containing $s^{\prime}$ becomes
crossing free after the flip. There are segments on both sides of $\ell$. If
$\ell$ separates $q,q^{\prime}$, then we untangle both sides independently
(Lemma 1.2) using $\mathcal{O}(n)$ and $\mathcal{O}(tn)$ flips (Theorem 3.5).
Otherwise, the segments on one side of $\ell$ are already crossing free
(because of the specific choice of $s^{\prime}$) and we inductively untangle
the $n^{\prime}\leq n-1$ segments on the other side of $\ell$ using
$f(n^{\prime})$ flips.

Case 2 ($\mathbf{CT\times CT\rightarrow CC,TT}$). If $s^{\prime}$ is a
$CT$-segment and one of the inserted segments is the $TT$-segment
$qq^{\prime}$, then the procedure is over as all crossings are on
$qq^{\prime}$.

Case 3 ($\mathbf{CT\times CT\rightarrow CT,CT}$). In this case two
$CT$-segments are inserted. Let $p\in C$ be an endpoint of $s=qp$. Since the
inserted $CT$-segment $q^{\prime}p$ is crossing free, Case 3 only happens
$\mathcal{O}(t)$ times before we arrive at Case 1 or Case 2.

Putting the three cases together, we obtain the recurrence

$f(n)\leq\mathcal{O}(t)+f(n^{\prime})\text{, with }n^{\prime}\leq n-1,$

which solves to $f(n)=\mathcal{O}(tn)$, as claimed.

We are now ready to prove the theorem.

######  Theorem 3.13.

Consider a multigraph $(P,S)$ with $P=C\cup T$ where $C$ is in convex
position, and $T=\\{q,q^{\prime}\\}$ such that $q$ is outside the convex hull
of $C$ and $q^{\prime}$ is inside the convex hull of $C$. Let $n=|S|$ and $t$
be the number of $T$-segments. There exists an untangle sequence of length
$\mathcal{O}(d_{\text{conv}}(n)+\delta(q)\delta(q^{\prime})n)=\mathcal{O}(d_{\text{conv}}(n)+t^{2}n)$
using only removal choice, where $d_{\text{conv}}(n)$ is the number of flips
to untangle any multiset of at most $n$ segments with endpoints in convex
position.

######  Proof 3.14.

The untangle sequence contains four phases.

Phase 1 ($\mathbf{CC\times CC}$). In this phase, we remove all crossings
between pairs of $CC$-segments using $d_{\text{conv}}(n)$ flips. Throughout
all the phases, the invariant that no pair of $CC$-segments crosses is
preserved.

Phase 2 ($\mathbf{Cq^{\prime}\times CC}$). In this phase, we remove all
crossings between pairs composed of a $CC$-segment and a $CT$-segment incident
to $q^{\prime}$ (the point inside the convex hull of $C$) using
$\mathcal{O}(tn)$ flips by Theorem 3.5.

Phase 3 ($\mathbf{Cq}$). At this point, all crossings involve a segment
incident to $q$. In this phase, we deal with all remaining crossings except
the crossings involving the segment $qq^{\prime}$. Lemma 1.2 allows us to
remove the crossings in each $CT$-segment $s$ incident to $q$ independently,
which we do using $\mathcal{O}(\delta(q^{\prime})n)$ flips using Lemma 3.11.
As there are $\delta(q)$ $CT$-segments adjacent to $q$, the total number of
flips is $\mathcal{O}(\delta(q)\delta(q^{\prime})n)=\mathcal{O}(t^{2}n)$.

Phase 4 ($\mathbf{CC\times TT}$). At this point, all crossings involve the
$TT$-segment $qq^{\prime}$. The endpoints in $C$ that are adjacent to segments
with crossings, together with $q^{\prime}$, are all in convex position. Hence,
the only endpoint not in convex position is $q$, and we apply Theorem 3.5
using $\mathcal{O}(tn)$ flips.

After the $d_{\text{conv}}(n)$ flips in Phase 1, the number of flips is
dominated by Phase 3 with
$\mathcal{O}(\delta(q)\delta(q^{\prime})n)=\mathcal{O}(t^{2}n)$ flips.

Notice that, in certain cases (for example in the red-blue case with
$q,q^{\prime}$ having different colors) a flip between two $CT$-segments never
produces two $CT$-segments. Consequently, Case 3 of the proof of Lemma 3.11
never happens, and the bound in Theorem 3.13 decreases to
$\mathcal{O}(d_{\text{conv}}(n)+tn)$.

##  4 Removal and Insertion Choices

In this section, we show how to untangle a matching or a multigraph using both
removal and insertion choices. We start with the case of points outside the
convex separated by two parallel lines. Afterwards, we prove an important
lemma and apply it to untangle a matching with points outside the convex.

###  4.1 Separated by Two Parallel Lines

We start with the simpler case in which $T$ is separated from $C$ by two
parallel lines. In this case, our bound of $\mathcal{O}(n+t|P|)$ interpolates
the tight convex bound of $\mathcal{O}(n)$ from [7] and the
$\mathcal{O}(t|P|)$ bound from [9] for $t$ arbitrary segments.

######  Theorem 4.1.

Consider a multigraph $(P,S)$ with $P=C\cup T_{1}\cup T_{2}$ where $C$ is in
convex position and there exist two horizontal lines $\ell_{1},\ell_{2}$, with
$T_{1}$ above $\ell_{1}$ above $C$ above $\ell_{2}$ above $T_{2}$. Let
$n=|S|$, $T=T_{1}\cup T_{2}$, and $t$ be the number of $T$-segments. There
exists an untangle sequence of length $\mathcal{O}(n+t|P|)=\mathcal{O}(tn)$
using both removal and insertion choices.

######  Proof 4.2.

The algorithm runs in two phases.

Phase 1. We use removal choice to perform the flips involving a point in $T$.
At the end of the first phase, there can only be crossings among segments with
all endpoints in $C$. The insertion choice for the first phase is the
following. Let $p_{1},\ldots,p_{|P|}$ be the points $P$ sorted vertically from
top to bottom. Consider a flip involving the points $p_{a},p_{b},p_{c},p_{d}$
with $a<b<c<d$. The insertion choice is to create the segments $p_{a}p_{b}$
and $p_{c}p_{d}$. As in [9], we define the potential $\eta$ of a segment
$p_{i}p_{j}$ as $\eta(p_{i}p_{j})=|i-j|$. Notice that $\eta$ is an integer
from $1$ to $|P|-1$. We define $\eta(S)$ as the sum of $\eta(p_{i}p_{j})$ for
$p_{i}p_{j}\in S$ with $p_{i}$ or $p_{j}$ in $T$. Notice that
$0<\eta(S)<t|P|$. It is easy to verify that any flip involving a point in $T$
decreases $\eta(S)$. Hence, the number of flips in Phase 1 is
$\mathcal{O}(t|P|)$.

Phase 2. Since $T$ is outside the convex hull of $C$, flips between segments
with all endpoints in $C$ cannot create crossings with the other segments,
which are guaranteed to be crossing free at this point. Hence, it suffices to
run an algorithm to untangle a convex set with removal and insertion choice
from [7], which performs $\mathcal{O}(n)$ flips.

###  4.2 Liberating a Line

In this section, we prove the following key lemma, which we use in the
following section. The lemma only applies to matchings and it is easy to find
a counter-example for multisets ($S$ consisting of $n$ copies of a single
segment that crosses $pq$).

######  Lemma 4.3.

Consider a matching $S$ of $n$ segments with endpoints $C$ in convex position,
and a segment $pq$ separating $C$. Using $\mathcal{O}(n)$ flips with removal
and insertion choices on the initial set $S\cup\\{pq\\}$, we obtain a set of
segments that do not cross the line $pq$.

######  Proof 4.4.

For each flip performed in the subroutine described hereafter, at least one of
the inserted segments does not cross the line $pq$ and is removed from $S$
(see Figure 9).

Figure 9: An untangle sequence of the subroutine to liberate the line $pq$
(with $n=4$).

Preprocessing. First, we remove from $S$ the segments that do not intersect
the line $pq$, as they are irrelevant. Second, anytime two segments in $S$
cross, we flip them choosing to insert the pair of segments not crossing the
line $pq$. One such flip removes two segments from $S$. Let $p_{1}p_{2}$
(respectively $p_{2n-1}p_{2n}$) be the segment in $S$ whose intersection point
with $pq$ is the closest from $p$ (respectively $q$). Without loss of
generality, assume that the points $p_{1}$ and $p_{2n-1}$ are on the same side
of the line $pq$.

First flip. Lemma A.1 applied to the segment $pq$ and the triangle
$p_{1}p_{2}p_{2n-1}$ shows that at least one of the segments among
$pp_{2n-1},qp_{1},qp_{2}$ intersects all the segments of $S$. Without loss of
generality, assume that $pp_{2n-1}$ is such a segment, i.e., that $pp_{2n-1}$
crosses all segments of $S\setminus\\{p_{2n-1}p_{2n}\\}$. We choose to remove
the segments $pq$ and $p_{2n-1}p_{2n}$, and we choose to insert the segments
$pp_{2n-1}$ and $qp_{2n}$. As the segment $qp_{2n}$ does not cross the line
$pq$, we remove it from $S$.

Second flip. We choose to flip the segments $pp_{2n-1}$ and $p_{1}p_{2}$. If
$n$ is odd, we choose to insert the pair of segments $pp_{1},p_{2}p_{2n-1}$.
If $n$ is even, we insert the segments $pp_{2},p_{1}p_{2n-1}$.

By convexity, one of the inserted segment (the one with endpoints in $C$)
crosses all other $n-2$ segments. The other inserted segment (the one with $p$
as one of its endpoints) does not cross the line $pq$, so we remove it from
$S$. Note that the condition on the parity of $n$ is there only to ensure that
the last segment $p_{2n-3}p_{2n-2}$ is dealt with at the last flip.

Remaining flips. We describe the third flip. The remaining flips are performed
similarly. Let $s$ be the previously inserted segment. Let $p_{3}p_{4}$ be the
segment in $S$ whose intersection point with $pq$ is the closest from $p$.
Without loss of generality, assume that $p_{3}$ is on the same side of the
line $pq$ as $p_{1}$ and $p_{2n-1}$.

We choose to flip $s$ with $p_{3}p_{4}$. If $s=p_{2}p_{2n-1}$, we choose to
insert the pair of segments $p_{2}p_{4},p_{3}p_{2n-1}$. If $s=p_{1}p_{2n-1}$,
we choose to insert the pair of segments $p_{1}p_{3},p_{4}p_{2n-1}$.

By convexity, one inserted segment (the one with $p_{2n-1}$ as an endpoint)
crosses all other $n-3$ segments. The other inserted segment does not cross
the line $pq$, so we remove it from $S$. Note that the insertion choice
described is the only viable one, as the alternative would insert a crossing-
free segment crossing the line $pq$ that cannot be removed.

###  4.3 Points Outside a Convex

We are now ready to prove the following theorem, which only applies to
matchings because it uses Lemma 4.3.

######  Theorem 4.5.

Consider a matching $S$ consisting of $n$ segments with endpoints $P=C\cup T$
where $C$ is in convex position and $T$ is outside the convex hull of $C$. Let
$t=|T|$. There exists an untangle sequence of length $\mathcal{O}(t^{3}n)$
using both removal and insertion choices.

######  Proof 4.6.

Throughout this proof, we partition the $TT$-segments into two types: _$TTI$
-segment_ if it intersects the interior of the convex hull of $C$ and _$TTO$
-segment_ otherwise.

$\mathbf{TT}$-segments. At any time during the untangle procedure, if there is
a $TTI$-segment $s$ that crosses more than $t$ segments, we apply Lemma 4.3 to
liberate $s$ from every $CC$-segment using $\mathcal{O}(n)$ flips. Let $\ell$
be the line containing $s$. Since $\lambda(\ell)$ cannot increase (Lemma 1.1),
$\lambda(\ell)<t$ after Lemma 4.3, and there are $\mathcal{O}(t^{2})$
different $TTI$-segments, it follows that Lemma 4.3 is applied
$\mathcal{O}(t^{2})$ times, performing a total $\mathcal{O}(t^{2}n)$ flips. As
the number of times $s$ is inserted and removed differ by at most $1$ and
$\lambda(\ell)$ decreases at each flip that removes $s$, it follows that $s$
participates in $\mathcal{O}(t)$ flips. As there are $\mathcal{O}(t^{2})$
different $TTI$-segments, the total number of flips involving $TTI$-segments
is $\mathcal{O}(t^{3})$.

We define a set $L$ of $\mathcal{O}(t)$ lines as follows. For each point $q\in
T$, we have two lines $\ell_{1},\ell_{2}\in L$ that are the two tangents of
the convex hull of $C$ that pass through $q$. As the lines $\ell\in L$ do not
separate $C$, the potential $\lambda(\ell)=\mathcal{O}(t)$. When flipping a
$TTO$-segment $q_{1}q_{2}$ with another segment $q_{3}p$ with $q_{3}\in T$
($p$ may be in $T$ or in $C$), we make the insertion choice of creating a
$TTO$-segment $q_{1}q_{3}$ such that there exists a line $\ell\in L$ whose
potential $\lambda(\ell)$ decreases. It is easy to verify that $\ell$ always
exist (see Lemmas B.1 and B.3 in the Appendix). Hence, the number of flips
involving $TTO$-segments is $\mathcal{O}(t^{2})$ and the number of flips
involving $TT$-segments in general is $\mathcal{O}(t^{3})$.

All except pairs of $\mathbf{CC}$-segments. We keep flipping segments that are
not both $CC$-segments with the following insertion choices. Whenever we flip
two $CT$-segments, we make the insertion choice of creating a $TT$-segment.
Hence, as the number of flips involving $TT$-segments is $\mathcal{O}(t^{3})$,
so is the number of flips of two $CT$-segments.

Whenever we flip a $CT$-segment $p_{1}q$ with $q\in T$ and a $CC$-segment
$p_{3}p4$, we make the following insertion choice. Let $v(q)$ be a vector such
that the dot product $v(q)\cdot q<v(q)\cdot p$ for all $p\in C$, that is, $v$
is orthogonal to a line $\ell$ separating $q$ from $C$ and pointing towards
$C$. We define the potential $\eta(p_{x}q)$ of a segment with $p_{x}\in C$ and
$q\in T$ as the number of points $p\in C$ such that $v(q)\cdot p<v(q)\cdot
p_{x}$, that is the number of points in $C$ before $p_{x}$ in direction $v$.
We choose to insert the segment $p_{x}q$ that minimizes $\eta(p_{x}q)$ for
$x=\\{1,2\\}$. Let $\eta(S)$ be the sum of $\eta(p_{x}q)$ for all
$CT$-segments $p_{x}q$ in $S$. It is easy to see that $\eta(S)$ is
$\mathcal{O}(t|C|)$ and decreases at each flip involving a $CT$-segment (not
counting the flips inside Lemma 4.3).

There are two situation in which $\eta(S)$ may increase. One is when Lemma 4.3
is applied, which happens $\mathcal{O}(t^{2})$ times. Another one is when a
$TT$-segment and a $CC$-segment flip, creating two $CT$-segments, which
happens $\mathcal{O}(t^{3})$ times. At each of these two situations, $\eta(S)$
increases by $\mathcal{O}(|C|)$. Consequently, the number of flips between a
$CT$-segment and a $CC$-segment is
$\mathcal{O}(t^{3}|C|)=\mathcal{O}(t^{3}n)$.

$\mathbf{CC}$-segments. By removal choice, we choose to flip the pairs of
$CC$-segments last (except for the ones flipped in Lemma 4.3). As $T$ is
outside the convex hull of $C$, flipping two $CC$-segments does not create
crossings with other segments (Lemma 1.2). Hence, we apply the algorithm from
[7] to untangle the remaining segments using $\mathcal{O}(n)$ flips.

## References

  * [1] Oswin Aichholzer, Brad Ballinger, Therese Biedl, Mirela Damian, Erik D Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Josef Tkadlec, and Yushi Uno.  Reconfiguration of non-crossing spanning trees.  arXiv preprint, 2022.  URL: https://arxiv.org/abs/2206.03879.
  * [2] Oswin Aichholzer, Kristin Knorr, Maarten Löffler, Zuzana Masárová, Wolfgang Mulzer, Johannes Obenaus, Rosna Paul, and Birgit Vogtenhuber.  Flipping plane spanning paths.  In International Conference and Workshops on Algorithms and Computation (WALCOM), 2023.  URL: https://arxiv.org/abs/2202.10831, doi:10.1007/978-3-031-27051-2_5.
  * [3] Oswin Aichholzer, Wolfgang Mulzer, and Alexander Pilz.  Flip distance between triangulations of a simple polygon is NP-complete.  Discrete & Computational Geometry, 54(2):368–389, 2015.  doi:10.1007/s00454-015-9709-7.
  * [4] Selim G Akl, Md Kamrul Islam, and Henk Meijer.  On planar path transformation.  Information processing letters, 104(2):59–64, 2007.  doi:10.1016/j.ipl.2007.05.009.
  * [5] Sergey Bereg and Hiro Ito.  Transforming graphs with the same degree sequence.  In Computational Geometry and Graph Theory, pages 25–32, 2008.  doi:10.1007/978-3-540-89550-3_3.
  * [6] Sergey Bereg and Hiro Ito.  Transforming graphs with the same graphic sequence.  Journal of Information Processing, 25:627–633, 2017.  doi:10.2197/ipsjjip.25.627.
  * [7] Ahmad Biniaz, Anil Maheshwari, and Michiel Smid.  Flip distance to some plane configurations.  Computational Geometry, 81:12–21, 2019.  URL: https://arxiv.org/abs/1905.00791, doi:10.1016/j.comgeo.2019.01.008.
  * [8] Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa.  The perfect matching reconfiguration problem.  In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 138 of LIPIcs, pages 80:1–80:14, 2019\.  doi:10.4230/LIPIcs.MFCS.2019.80.
  * [9] Édouard Bonnet and Tillmann Miltzow.  Flip distance to a non-crossing perfect matching.  arXiv, 1601.05989, 2016.  URL: http://arxiv.org/abs/1601.05989.
  * [10] Nicolas Bousquet and Alice Joffard.  Approximating shortest connected graph transformation for trees.  In Theory and Practice of Computer Science, pages 76–87, 2020.  doi:10.1007/978-3-030-38919-2_7.
  * [11] Jou-Ming Chang and Ro-Yu Wu.  On the diameter of geometric path graphs of points in convex position.  Information processing letters, 109(8):409–413, 2009.  doi:10.1016/j.ipl.2008.12.017.
  * [12] Guilherme D. da Fonseca, Yan Gerard, and Bastien Rivier.  On the longest flip sequence to untangle segments in the plane.  In International Conference and Workshops on Algorithms and Computation (WALCOM), volume to appear of Lecture Notes in Computer Science, 2023.  URL: https://arxiv.org/abs/2210.12036, doi:10.1007/978-3-031-27051-2_10.
  * [13] Arun Kumar Das, Sandip Das, Guilherme D. da Fonseca, Yan Gerard, and Bastien Rivier.  Complexity results on untangling red-blue matchings.  Computational Geometry, 111:101974, 2023.  URL: https://arxiv.org/abs/2202.11857, doi:10.1016/j.comgeo.2022.101974.
  * [14] Matthias Englert, Heiko Röglin, and Berthold Vöcking.  Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP.  Algorithmica, 68(1):190–264, 2014.  doi:10.1007/s00453-013-9801-4.
  * [15] Péter L Erdős, Zoltán Király, and István Miklós.  On the swap-distances of different realizations of a graphical degree sequence.  Combinatorics, Probability and Computing, 22(3):366–383, 2013.  doi:10.1017/S0963548313000096.
  * [16] Branko Grünbaum.  Polygons in arrangements generated by n points.  Mathematics Magazine, 46(3):113–119, 1973.  doi:10.1080/0025570X.1973.11976293.
  * [17] Seifollah Louis Hakimi.  On realizability of a set of integers as degrees of the vertices of a linear graph. I.  Journal of the Society for Industrial and Applied Mathematics, 10(3):496–506, 1962.
  * [18] Seifollah Louis Hakimi.  On realizability of a set of integers as degrees of the vertices of a linear graph II. uniqueness.  Journal of the Society for Industrial and Applied Mathematics, 11(1):135–147, 1963.
  * [19] Ferran Hurtado, Marc Noy, and Jorge Urrutia.  Flipping edges in triangulations.  Discrete & Computational Geometry, 22(3):333–346, 1999.
  * [20] Alice Joffard.  Graph domination and reconfiguration problems.  PhD thesis, Université Claude Bernard Lyon 1, 2020.
  * [21] Charles L Lawson.  Transforming triangulations.  Discrete Mathematics, 3(4):365–372, 1972.
  * [22] Anna Lubiw and Vinayak Pathak.  Flip distance between two triangulations of a point set is NP-complete.  Computational Geometry, 49:17–23, 2015.  doi:10.1016/j.comgeo.2014.11.001.
  * [23] Naomi Nishimura.  Introduction to reconfiguration.  Algorithms, 11(4), 2018.  doi:10.3390/a11040052.
  * [24] Yoshiaki Oda and Mamoru Watanabe.  The number of flips required to obtain non-crossing convex cycles.  In Kyoto International Conference on Computational Geometry and Graph Theory, pages 155–165, 2007.
  * [25] Alexander Pilz.  Flip distance between triangulations of a planar point set is APX-hard.  Computational Geometry, 47(5):589–604, 2014.  doi:10.1016/j.comgeo.2014.01.001.
  * [26] Jan van den Heuvel.  The complexity of change.  Surveys in Combinatorics, 409:127–160, 2013.
  * [27] Jan van Leeuwen and Anneke A. Schoone.  Untangling a traveling salesman tour in the plane.  In 7th Workshop on Graph-Theoretic Concepts in Computer Science, 1981.
  * [28] Todd G Will.  Switching distance between graphs with the same degrees.  SIAM Journal on Discrete Mathematics, 12(3):298–306, 1999.  doi:10.1137/S0895480197331156.
  * [29] Ro-Yu Wu, Jou-Ming Chang, and Jia-Huei Lin.  On the maximum switching number to obtain non-crossing convex cycles.  In 26th Workshop on Combinatorial Mathematics and Computation Theory, pages 266–273, 2009.

##  Appendix A Auxiliary Lemma of Section 4.2

In this section, we prove Lemma A.1 used in the proof of Lemma 4.3.

Recall that, in the proof of Lemma 4.3, we have a convex quadrilateral
$p_{1}p_{2}p_{2n}p_{2n-1}$ and a segment $pq$ crossing the segments
$p_{1}p_{2}$ and $p_{2n}p_{2n-1}$ in this order when drawn from $p$ to $q$,
and we invoke Lemma A.1 to show that at least one of the segments among
$pp_{2n-1},qp_{1},qp_{2}$ intersects all the segments of $S$. Before proving
Lemma A.1, we detail how to apply it to this context.

Lemma A.1 applied to the segment $pq$ and the triangle $p_{1}p_{2}p_{2n-1}$
asserts that at least one of the following pairs of segments cross:
$pp_{2n-1},p_{1}p_{2}$, or $qp_{1},p_{2}p_{2n-1}$, or $qp_{2},p_{1}p_{2n-1}$.
If the segments $pp_{2n-1},p_{1}p_{2}$ cross, then we are done. If the
segments $qp_{1},p_{2}p_{2n-1}$ cross, then the segments
$qp_{1},p_{2n}p_{2n-1}$ also cross and we are done. If the segments
$qp_{2},p_{1}p_{2n-1}$ cross, then the segments $qp_{2},p_{2n}p_{2n-1}$ also
cross and we are done.

Next, we state and prove Lemma A.1.

######  Lemma A.1.

For any triangle $abc$, for any segment $pq$ intersecting the interior of the
triangle $abc$, there exists a segment $s\in\\{pa,pb,pc,qa,qb,qc\\}$ that
intersects the interior of the triangle $abc$.

######  Proof A.2.

If all $a,b,c,p,q$ are in convex position, then $p$ and the point among
$a,b,c$ that is not adjacent to $p$ on the convex hull boundary define the
segment $s$. Otherwise, since $p,q$ are not adjacent on the convex hull
boundary, assume without loss of generality that $a$ is not a convex hull
vertex and $p,b,q,c$ are the convex hull vertices in order. Then, either $ap$
or $aq$ intersects $bc$.

##  Appendix B Auxiliary Lemmas of Section 4.3

In this section, we prove Lemma B.3 and Lemma B.1 used in the proof of Theorem
4.5.

Recall that, in the proof of Theorem 4.5, we define a set $L$ of lines as
follows. For each point $q\in T$, we have two lines $\ell_{1},\ell_{2}\in L$
that are the two tangents of the convex hull of $C$ that pass through $q$.
When flipping a $TTO$-segment $q_{1}q_{2}$ with another segment $q_{3}p$ with
$q_{3}\in T$ ($p$ may be in $T$ or in $C$), we make the insertion choice of
creating a $TTO$-segment $q_{1}q_{3}$ such that there exists a line $\ell\in
L$ whose potential $\lambda(\ell)$ decreases. We invoke Lemma B.1 and Lemma
B.3 to show that such a line $\ell$ always exist.

Indeed, by Lemma B.1, it is enough to show that there exists a line $\ell\in
L$ containing one of the points $q_{1},q_{2},q_{3}$ that crosses one of the
segments $q_{1}q_{2}$ or $q_{3}p$. This is precisely what Lemma B.3 shows.

Next, we state prove Lemma B.1 and Lemma B.3.

######  Lemma B.1.

Consider two crossing segments $p_{1}p_{2},p_{3}p_{4}$ and a line $\ell$
containing $p_{1}$ and crossing $p_{3}p_{4}$. Then, one of the two pairs of
segments $p_{1}p_{3},p_{2}p_{4}$ or $p_{1}p_{4},p_{2}p_{3}$ does not cross
$\ell$. In other words, there exists an insertion choice to flip
$p_{1}p_{2},p_{3}p_{4}$ such that the number of segments crossing $\ell$
decreases.

######  Proof B.2.

Straightforward.

######  Lemma B.3.

Consider a closed convex body $B$ and two crossing segments
$q_{1}q_{3},q_{2}q_{4}$ whose endpoints $q_{1},q_{2},q_{3}$ are not in $B$,
and whose endpoint $q_{4}$ is not in the interior of $B$. If the segment
$q_{1}q_{3}$ does not intersect the interior of $B$, then at least one of the
six lines tangent to $B$ and containing one of the endpoints
$q_{1},q_{2},q_{3}$ is crossing one of the segments $q_{1}q_{3},q_{2}q_{4}$.
(General position is assumed, meaning that the aforementioned six lines are
distinct, i.e., each line does not contain two of the points
$q_{1},q_{2},q_{3},q_{4}$.)

[b]
(a) [b]
(b)

Figure 10: (a) In the statement of Lemma B.3, we assert the existence of
points, circled in the figure, which are the intersection of a line tangent to
$B$ and containing one of the points $q_{1},q_{2},q_{3}$. (b) In the proof of
Lemma B.3 by contraposition, we exhibit a point, circled in the figure,
showing that $B$ intersects one of the segment $q_{1}q_{3}$.

######  Proof B.4.

For all $i\in\\{1,2,3\\}$, let $\ell_{i}$ and $\ell_{i}^{\prime}$ be the two
lines containing $q_{i}$ and tangent to $B$. By contraposition, we assume that
none of the six lines
$\ell_{1},\ell_{1}^{\prime},\ell_{2},\ell_{2}^{\prime},\ell_{3},\ell_{3}^{\prime}$
crosses one of the segments $q_{1}q_{3},q_{2}q_{4}$. In other words, we assume
that the six lines are tangent to the convex quadrilateral
$q_{1}q_{2}q_{3}q_{4}$. It is well known that, if $m\geq 5$, then any
arrangement of $m$ lines or more admits at most one face with $m$ edges (see
[16] for example). Therefore, $B$ is contained in the same face of the
arrangement of the six lines as the quadrilateral $q_{1}q_{2}q_{3}q_{4}$. Let
$p_{1}$ (respectively $p_{1}^{\prime}$) be a contact point between the line
$\ell_{1}$ (respectively $\ell_{1}^{\prime}$) and the convex body $B$. The
segment $p_{1}p_{1}^{\prime}$ crosses the segment $q_{1}q_{3}$ and is
contained in $B$ by convexity, concluding the proof by contraposition.