betaFeedback

WorksComputer Science

Quadratic Reconfiguration of Plane Spanning Paths on Two-Layer Point Sets

Abstract

Consider a crossing-free polygonal path with nn vertices and a flip operation that removes an edge and adds another one, without changing the vertex set and keeping the path crossing free. It is conjectured that any two such paths can be transformed into each other by a sequence of flips. Recently, Kleist et al. (2024) proved the conjecture for the special cases of vertices arranged in two convex layers. However, the number of flips in their proof may be exponential. In this paper, we show that O(n2)O(n^2) flips suffice. More precisely, for a two-layer point set S=L0∪L1S=L_0\cup L_1, where L0L_0 and L1L_1 denote the outer and inner layers, respectively, our method uses O(∣L0∣+∣L1∣2)O(|L_0|+|L_1|^2) flips.

Introduction

Reconfiguration studies a family of configurations that are changed into each other using a flip operation. In our case, the configurations are crossing-free spanning paths of a set SS of nn points and the flip operation removes an edge and adds another one while preserving a valid configuration. Given a set SS, there is an associated flip graph whose vertices are configurations and edges are defined by flips. The diameter of the flip graph is the number of flips needed, in the worst case, to transform one path into another. We refer to paths in the flip graph as flip sequences to avoid confusion. An example of flip sequence is drawn Figure 1.

Figure 1. A flip sequence connecting a pair of paths

The problem was introduced by [7] in 2001, together with an implicit conjecture that the flip graph is connected and a proof of it for the special cases of points SS in convex position (SS is the set of convex hull vertices). The first polynomial bound on the diameter for the convex case appears in [3], at most 2n−52n - 5. Later a tight bound of 2n−52n - 5 for n≤4n \le4 and 2n−62n - 6 for n≥5n \ge5 has been shown [5]. In the convex case, the shortest flip sequence can be computed in linear time [1].

Proving the conjecture for arbitrary point sets remains challenging and many authors considered several other special cases; we cite the most relevant for this paper. For convex position plus one interior point, the diameter is at most 2n−42n-4 [2]. For convex position plus one exterior point, the diameter is at most 2n2n [4]. Both cases are special cases of a more general two-layer point set S=L0∪L1S=L_0\cup L_1 where the outer layer L0L_0 is the set of vertices in the convex hull of SS and the inner layer L1L_1 is also in convex position. In [6], they show that the flip graph for two layers is connected, but the diameter implied by their proof is exponential. In this paper, we prove the following quadratic bound.

Theorem 1. For a two-layer point set S=L0∪L1S=L_0\cup L_1, where L0L_0 and L1L_1 denote the outer and inner layers, the diameter of the flip graph is O(∣L0∣+∣L1∣2)O(|L_0|+|L_1|^2) and computing a flip sequence connecting a pair of paths takes O(∣L0∣+∣L1∣2)O(|L_0|+|L_1|^2) time.

Canonical Paths and Potential Reduction

This section assembles the main elements allowing us to prove Theorem 1. Let S=L0∪L1S=L_0\cup L_1 be a two-layer point set with L0L_0 and L1L_1 the outer and inner layer respectively. Let n0=∣L0∣n_0=|L_0| and n1=∣L1∣n_1=|L_1|.

We first prove the connectivity of a particular family of paths that we will call canonical paths (Subsection 2.2). The second step is to show that any arbitrary plane spanning path on a two-layer point set can be transformed into a canonical path. We achieve this goal by defining a potential function Φ\Phi on paths (subsection 2.3). The potential has three properties (subsection 2.4):

  • the potential of a path is 1 if and only if that path is canonical

  • the potential is strictly positive, so that the set of the canonical paths is exactly the class of paths with minimum potential

  • if the potential of a path is not minimal i.e if the path is not canonical, we provide an algorithm for getting a sequence of flips decreasing the potential by at least 1. The number of flips required for a potential decreasing is precisely the key explaining the bound on the diameter of the flip graph given in Theorem 1.

In other words, a sequence of flips decreasing the potential of a path until the minimum value 1 transforms the initial path into a canonical path. As all the canonical paths are connected, the connection of any path to a canonical path proves the connectivity of the whole flip graph. It yields Theorem 1.

Terminology

Before starting to define the canonical paths and the potential, we introduce some notations. For two vertices uu, v∈Sv \in S in a path PP, we say that uu sees vv if the interior of the segment uvuv does not intersect any other edge of PP.

To distinguish the neighbors of the vertices in a path, we may orient the path. When a path is oriented, its first and last vertices are called the start and end, respectively. An stst-path is an oriented path with start ss and end tt. For a vertex uu, we denote by in⁡(u)\operatorname{in}(u) and out⁡(u)\operatorname{out}(u) its incoming and outgoing edges, when they exist. We write pred⁡(u)\operatorname{pred}(u) and succ⁡(u)\operatorname{succ}(u) for the predecessor and successor of uu, respectively. Whenever an edge is written as uvuv in an oriented path, we implicitly assume that u=pred⁡(v)u = \operatorname{pred}(v).

For an stst-path PP, the subpath from u∈Su \in S to v∈Sv \in S is denoted by P[u:v]P[u : v]. A prefix of the path is any subpath of the form P[s:u]P[s : u], u∈Su \in S, and a suffix of the path is any path of the form P[u:t]P[u : t], u∈Su \in S.

Reconfiguration of Canonical Paths

A path is canonical if it first visits all vertices of one layer in cyclic order and then all vertices of the other layer in cyclic order. The directions chosen on the two layers do not need to be the same. For instance, all paths in Figure 2 are canonical.

Counterclockwise bridge shift on the inner layer

Figure 2. Counterclockwise bridge shift on the inner layer

The unique edge of a canonical path connecting an outer point to an inner point is called a bridge. A canonical path is completely determined by its bridge, and, for each layer, the direction (clockwise or counterclockwise) in which the path traverses that layer from the corresponding extremity of the bridge.

To reconfigure canonical paths, two useful observation can be made:

  • The traversal direction of either layer can be reversed in 1 flip.

  • Either extremity of the bridge can be shifted to their layer neighbor they are not connected with in 1 flip, if it does not introduce crossing.

Using these observations, we can reconfigure canonical paths in linear flips while preserving their structure.

Lemma 2. The subgraph of the flip graph of canonical paths on a two-layer point set is connected with diameter O(n0+n1)O(n_0 + n_1) flips.

Proof. Let PP and P′P' be two canonical paths with bridges uvuv and u′v′u'v', where u,u′∈L0u,u' \in L_0 and v,v′∈L1v,v' \in L_1.

Consider a triangulation of the ring between L0L_0 and L1L_1 that contains both uvuv and u′v′u'v' and such that and no triangle connects three points of L0L_0. In such a triangulation, the edges joining L0L_0 and L1L_1 form a cyclic sequence TT where each consecutive edge differ only by one endpoint.

Fix a direction along this sequence, say counterclockwise. First, if necessary, flip the edges adjacent to the bridge to connect uu and vv to ccw⁡(u)\operatorname{ccw}(u) and ccw⁡(v)\operatorname{ccw}(v) respectively.

Starting from uvuv, repeatedly flip the bridge to the next one of TT in counterclockwise direction, and do another flip to connect the extremity of the bridge that shifted to its clockwise neighbor again. An Illustration of these two flips is given in Figure 2 This second flip preserves the loop invariant that the path is always a canonical path in which both extremities of the bridge are connected to their clockwise neighbor.

Repeating this process eventually transforms the bridge uvuv into u′v′u'v'. Finally, at most two additional flips are needed to adjust the traversal directions on the two layers so that the resulting canonical path is exactly P′P'.

At the end of that loop we can correct the orientation of the path at the extremity of the bridge to match P′P' in 2 flips. Therefore PP can be transformed into P′P'.

Moreover, the sequence TT contains exactly n0+n1n_0+n_1 edges. So the whole process uses at most 2(n0+n1)+42(n_0+n_1)+4 flips, proving the claim. □\square

Potential

We now introduce the potential used for connecting any path to a canonical path. Its value is based on a classification of edges according to their position with respect to the two layers. We distinguish five types of edges:

  • level edges, joining two consecutive vertices on the same layer;

  • bridges, joining an outer and an inner vertex without crossing the convex hull of L1L_1;

  • small diagonals, joining two non-consecutive vertices of L1L_1;

  • medium diagonals, joining an outer and an inner vertex through the interior of the convex hull of L1L_1;

  • big diagonals, joining two non-consecutive vertices of L0L_0.

These edge types are represented in Figure 3.

Illustration of the five edge types in a two-layer point set

Figure 3. Illustration of the five edge types in a two-layer point set.

We assign a weight to each edge type and define the potential Φ(P)\Phi(P) of a path PP as

Φ(P)=0L(P)+1B(P)+1S(P)+3M(P)+4G(P)(1)\Phi(P) = 0L(P) + 1B(P) + 1S(P) + 3M(P) + 4G(P) \tag*{(1)}

where L(P)L(P), B(P)B(P), S(P)S(P), M(P)M(P) and G(P)G(P) denote the numbers of level edges, bridges, small diagonals, medium diagonals and big diagonals in PP, respectively. The coefficients in (1) are chosen so that canonical paths are exactly the paths of minimum potential.

Potential Properties and Proof of Theorem 1

The first properties are straightforward. First, by definition, the potential is a strictly positive integer. Secondly, paths of minimal potential are canonical:

Lemma 3. The minimum value of Φ\Phi is 1, and a path has potential 1 if and only if it is canonical.

Proof. Every spanning path must contain an edge joining the two layers. Such an edge is either a bridge or a medium diagonal, both of which contribute at least 1 to the potential. Therefore Φ(P)≥1\Phi(P) \ge1 for every path PP.

Now let PP be a path with Φ(P)=1\Phi(P) = 1. Since every edge type except level edges has weight at least 1, the path must contain exactly one bridge and all its remaining n0+n1−2n_0 + n_1 - 2 edges must be level edges.

Consequently, the restriction of PP to L0L_0 contains exactly n0−1n_0 - 1 level edges and the restriction of PP to L1L_1 contains exactly n1−1n_1 - 1 level edges. Hence the vertices of each layer are traversed consecutively in cyclic order. The unique bridge connects the two layer-traversals, so PP is a canonical path.

Conversely, every canonical path consists of a single bridge and n0+n1−2n_0 + n_1 - 2 level edges, and therefore has potential 1. □\square

Lemma 4. If a path is not canonical, we can reduce its potential by at least 1 with a sequence of at most O(n1)O(n_1) flips.

Lemma 5. Throughout the process of diminishing the potential of the path, at most O(n1)O(n_1) potential reduction steps require more than 1 flip.

These last two lemmas enable the proof of Theorem 1.

Proof (Theorem 1). Let PP be a path. By Lemma 4, we can diminish its potential in at most O(n1)O(n_1) flips, until it has least potential and becomes canonical (Lemma 3). Among each of these reduction steps, at most O(n1)O(n_1) of them may require more than 1 flip to be performed, according to Lemma 5. Therefore, since Φ(P)=\Phi(P) = O(n0+n1)O(n_0+n_1), this means that the reconfiguration of PP into a canonical path requires at most O(n0+n12)O(n_0+n_1^2).

Moreover, using Lemma 2, we can reconfigure any canonical paths into one another in O(n0+n1)O(n_0+n_1) flip, meaning we can reconfigure any path into one another in O(n0+n12)O(n_0+n_1^2) flips. □\square

The later material in Sections 3, 7 and 5 are respectively devoted to the proofs of Lemma 4 and Lemma 5. An organization of the dependencies between the previous and next claims is illustrated in Figure 4

The tree of dependencies of the different lemmas allowing us to prove Theorem 1

Figure 4. The tree of dependencies of the different lemmas allowing us to prove Theorem 1

Potential Reduction

In this section, we provide a sketch of proof of Lemma 4. The different procedures constituting the algorithm leading to this lemma and their respective proof of correction are given in Section 4.

To this end, we describe an algorithm that, given a path PP with Φ(P)>1\Phi(P)>1, performs a sequence of flips that decreases the potential. The algorithm uses two different procedures, depending on whether an endpoint of PP is on the outer layer or if both are in the inner layer. We give a high level description of these procedures.

The procedure OuterReduction takes as input an oriented path whose start vertex lies on the outer layer. Its goal is to create a new level edge incident to the start. When such an edge cannot be created immediately, it tries the same thing with the end. If this fails again, the procedure uses its end vertex to change the orientation of the path next to the start vertex, so that a new level edge incident to the start can be created. This procedure performs a constant flip sequence.

Lemma 6. Let PP be an stst-path where the start s∈L0s \in L_0 is an outerpoint. Then the procedure OuterReduction reduces the potential of the path in O(1)O(1) flips.

The procedure InnerReduction handles the case where both endpoints lie on the inner layer. As before, the primary objective is to create a new level edge incident to the start vertex. If this fails, depending on the type of the incoming edge of the layer neighbor of the start, the procedure either performs a direct reduction or transforms the path into a simpler configuration that admits further reductions. This procedure may perform O(n1)O(n_1) flips in certain cases.

Lemma 7. Let PP be an stst-path where both endpoints are in L1L_1. Then the procedure InnerReduction reduces the potential of the path in O(n1)O(n_1) flips.

The two lemmas 6 and 7 directly imply Lemma 4. Their two procedures OuterReduction and InnerReduction may invoke some common subprocedures ObstrReduction and DiagObstrReduction when common cases arise. These two subprocedures handle cases where some visibility between some points are obstructed by some edges of the path. These cases always involve edges with heavy weight, so the goal of these subprocedures is to find a way to flip them.

Lemma 8. Let PP be a path starting at s∈L1s \in L_1 and let qq be a neighbor not seen by ss because some edge of PP blocks the visibility between them. Then the procedure ObstrReduction reduces the potential of the path in O(1)O(1) flips.

Lemma 9. Let PP be a path starting at s∈L1s \in L_1. Suppose that PP contains a diagonal uvuv, where either uvuv is a big diagonal or uvuv is a medium diagonal with uu a cyclic neighbor of ss in L1L_1. Assume that ss sees uu but not vv, and that there exists an inner vertex p∈△suvp \in\triangle suv that sees both ss and vv. Moreover, assume that the concave quadrilateral suvpsuvp is empty.

Let u′u' be the last outer vertex on P[s:u]P[s:u] and let v′v' be the first neighbor of vv visited by PP. Assume further that

  1. P[s:p]P[s:p] lies entirely in L1L_1 and visits its vertices in cyclic order from ss to pp;

  2. and P[p:u′]P[p:u'] visits the remaining inner vertices between ss and pp, together with the outer vertices from v′v' to u′u', preserving their cyclic order on L0L_0.

Then DiagObstrReduction reduces the potential of PP using O(1)O(1) flips.

We detail the procedures and prove Lemmas 6 to 9 in the following section.

Procedures reducing the potential of a path

In this section, we provide the different procedures reducing the potential of a path, and prove their correctness and their complexity. We start by presenting the two main procedures, OuterReduction (§ 4.1) and InnerReduction (§ 4.2), and finish by the last two sub procedures ObstrReduction and DiagObstrReduction (§ 4.3).

Procedure OuterReduction and proof of Lemma 6

Procedure OuterReduction.

Input: a path PP whose start s∈L0s \in L_0 lies on the outer layer, and a neighbor s′s' of ss that does not share an edge with it. Assume s′=ccw⁡(s)s' = \operatorname{ccw}(s) by symmetry. Let tt be the end of the path.

  1. If s′=ts' = t, pick any non-level edge and flip it to stst.

  2. Else if the incoming edge of s′s' is not a level edge, flip it to ss′ss'.

  3. Otherwise: Let t′t' be a neighbor of tt that does not share an edge with it. (a) If t′t' does not see tt, reverse the order of the path and apply the ObstrReduction procedure on that obstruction. (b) Else if the outgoing edge of t′t' is not a level edge, flip it to tt′tt'. (c) Else if t′∈P[s:s′]t' \in P[s:s'], perform

out⁡(t′)⟶t′t,in⁡(s′)⟶ss′\operatorname{out}(t') \longrightarrow t't,\qquad\operatorname{in}(s') \longrightarrow ss'

(d) Otherwise, let uvuv, with u=pred⁡(v)u = \operatorname{pred}(v), be the last small diagonal in P[succ⁡(s′):t]P[\operatorname{succ}(s'):t], and let v′v' be neighbor of vv not seen by t′t'. Then perform uv⟶utuv \longrightarrow ut, and apply recursively OuterReduction using v′v' for the non connected neighbor of the new start vv.

Proof (Lemma 6). Let PP be an stst-path starting at s∈L0s \in L_0, and assume ∣L0∣≥3|L_0| \ge3, otherwise the lemma is trivial. Let s′∈L0s' \in L_0 be one of the cyclic neighbor of ss and assume s′=ccw⁡(s)s' = \operatorname{ccw}(s) by symmetry. Since these points are neighbors of the outer layer, they necessarily see each other.

Therefore the flips in Cases 1 and 2 are legal and decrease the potential.

So now suppose the premise of Case 3 is verified: the incoming edge of s′≠ts' \ne t is a level edge. Then the path has a particular structure. Indeed, as illustrated in Figure 5, the prefix P[s:s′]P[s:s'] wraps around the suffix P[succ⁡(s′):t]P[\operatorname{succ}(s'):t] so that the latter is forced to stay confined in L1L_1. In particular, the end t∈L1t \in L_1 is an inner point. This restriction on the suffix means that P[s:s′]P[s:s'] must visit all outer points, and we can prove that all the points from L0L_0 must appear in a cyclic order in that prefix.

Structure of the path in Case 3 of procedure OuterReduction

Figure 5. Structure of the path in Case 3 of procedure OuterReduction

Also, since the incoming edge of s′s' is a level edge, its outgoing edge is not as s′s' does not share an edge with ss. So the remaining cases try to reverse the orientation of the path in s′s' if it cannot be immediately be reduced near tt.

Let t′∈L1t' \in L_1 be a neighbor of tt such that t′t' does not share an edge with tt. Such a t′t' always exists unless ∣L1∣≤2|L_1| \le2 and the path already has potential 1. We distinguish cases depending on visibility between tt and t′t' and the type of the outgoing edge of t′t'.

  • Case 3.(a): If tt does not see t′t', then applying ObstrReduction reduces the potential in O(1)O(1) according to Lemma 8.

  • Case 3.(b): If tt sees t′t' and the outgoing edge of t′t' is not a level edge, then out⁡(t′)→t′t\operatorname{out}(t') \to t't creates a new level edge, diminishing the potential.

Now let’s suppose that tt sees t′t', and out⁡(t′)\operatorname{out}(t') is a level edge.

  • Case 3.(c): If t′∈P[s:s′]t' \in P[s:s'] or equivalently s′∈P[t′:t]s' \in P[t':t], the first flip (out⁡(t′)→t′t)(\operatorname{out}(t') \to t't) is legal and does not change the potential. The second flip in⁡(s′)→ss′\operatorname{in}(s') \to ss' is also legal as s′s' sees ss. Moreover, after the first flip the orientation of the path in s′∈P[t′:t]s' \in P[t':t] is reversed, exchanging in⁡(s′)\operatorname{in}(s') with the non-level edge out⁡(s′)\operatorname{out}(s'). Therefore the second flip flips a non-level edge to a level edge, which diminishes the potential. The flip sequence produced is illustrated in Figure 6.

Reduction of potential in Case 3.(c) of Procedure OuterReduction

Figure 6. Reduction of potential in Case 3.(c) of Procedure OuterReduction.

  • Case 3.(d): Suppose t′∈P[succ⁡(s′):t]t' \in P[\operatorname{succ}(s'):t]. In this case, we can show that t′=succ⁡(s′)t' = \operatorname{succ}(s'). Indeed, if that was not the case, then as P[succ⁡(s′):t]⊂L1P[\operatorname{succ}(s'):t] \subset L_1 and out⁡(t′)\operatorname{out}(t') is a level edge, in⁡(t′)\operatorname{in}(t') must be a small diagonal. This diagonal would cut L1L_1 in two parts, separating succ⁡(t′)\operatorname{succ}(t') and t′t' the two neighbors of t′t' and introducing a crossing with the suffix P[succ⁡(t′):t]P[\operatorname{succ}(t'):t]. Therefore in this case t′=succ⁡(s′)t' = \operatorname{succ}(s').

From this observation we can deduce that P[t′:t]P[t':t] necessarily contains a small diagonal, as if it was not the case, P[t′:t]P[t':t] would visit all inner points in cyclic order, which would imply that the path is already canonical. Now, as in the procedure, let uvuv be the last diagonal of P[t′:t]P[t':t]. Then it splits L1L_1 in half and we can define v′v' to be the neighbor of vv not seen by t′t'. The flip uv→utuv \to ut does not necessarily decrease the potential, but it changes the end of the path to vv, so that applying again the procedure with v′v' for the choice of the neighbor of vv will not lead to that case again, since v′≠tv' \ne t so v′≠succ⁡(s′)v' \ne\operatorname{succ}(s'). And since all the other cases decrease the potential in O(1)O(1) flips, this one does as well. The flip sequence produced in this case is illustrated in Figure 7.

Reduction Case 3.(d) to other cases of procedure OuterReduction

Figure 7. Reduction Case 3.(d) to other cases of procedure OuterReduction

This proves by case analysis that the procedure OuterReduction can always reduce the potential of a non-canonical path with an outer endpoint in O(1)O(1) flips.

Procedure InnerReduction and proof of Lemma 7

Procedure InnerEndpointsReduce. Input: a path PP whose start s∈L1s \in L_1 and end t∈L1t \in L_1 lie on the inner layer, and a neighbor s′s' of ss that does not share an edge with it. Assume s′=ccw⁡(s)s' = \operatorname{ccw}(s) by symmetry.

  1. If ss does not see s′s', apply the ObstrReduction procedure on that obstruction.

  2. Else if the incoming edge of s′s' is not a level edge, flip it to ss′ss'.

  3. Else if s′=ts' = t, pick any non-level edge and flip it to ss′ss'.

  4. Else if the outgoing edge of s′s' is a small diagonal: Let x=succ⁡(s′)x = \operatorname{succ}(s'). Repeat until the potential decreases: let ss be the start of the path, and s′=ccw⁡(s)s' = \operatorname{ccw}(s), and perform

s′x→sx,in⁡(s)→s′s.s'x \to sx,\qquad\operatorname{in}(s) \to s's.
  1. Else if the outgoing edge of s′s' is a medium diagonal: Let x=succ⁡(s′)x = \operatorname{succ}(s'). If ss and tt are on the same side of s′xs'x in L1L_1, flip ccw⁡(s′)s′→ss′\operatorname{ccw}(s')s' \to ss', rename ccw⁡(s′)\operatorname{ccw}(s') as ss, and take the reflect the path so that s′=ccw⁡(s)s' = \operatorname{ccw}(s) again. Then (a) If xx sees ss, repeat until the potential decreases or ss no longer sees xx: let ss be the start of the path, and s′=ccw⁡(s)s' = \operatorname{ccw}(s), and perform

s′x→sx,in⁡(s)→s′s.s'x \to sx,\qquad\operatorname{in}(s) \to s's.

If the potential has not decreased, then follow the procedure DiagObstrReduction with the start ss and diagonal s′xs'x. (b) If xx does not see ss, follow the procedure DiagObstrReduction with the start ss and diagonal s′xs'x.

  1. Otherwise, the outgoing edge of s′s' is a bridge.

(a) If P[s:s′]⊄L1P[s:s'] \not\subset L_1, Let u=succ⁡(s′)u=\operatorname{succ}(s'). If s′s', uu, succ⁡(u)\operatorname{succ}(u) are not in clockwise order, flip ccw⁡(s′)s′\operatorname{ccw}(s')s' to ss′ss', rename ccw⁡(s′)\operatorname{ccw}(s') as ss, and reflect the path so that s′s' becomes ccw⁡(s)\operatorname{ccw}(s) again, and the order of s′s', uu, succ⁡(u)\operatorname{succ}(u) becomes clockwise. Let v=ccw⁡(u)v=\operatorname{ccw}(u) and v′=succ⁡(v)v'=\operatorname{succ}(v).

i. If ss sees v′v', perform vv′→sv′vv' \to sv', then s′u→vus'u \to vu.

ii. Else let pqpq be the last small diagonal of P[v′:s′]P[v':s'], with p=pred⁡(q)p=\operatorname{pred}(q), and let p′=ccw⁡(p)p'=\operatorname{ccw}(p). Then flip pq→sqpq \to sq and recursively apply InnerEndpointsReduce using p′p' as the neighbor of the new start pp.

(b) Otherwise P[s:s′]⊂L1P[s:s'] \subset L_1. Let uvuv be the first small diagonal of P[s:s′]P[s:s'], with u=pred⁡(v)u=\operatorname{pred}(v). let u′u' be the neighbor of uu not seen by s′s'. Then flip uvuv to svsv, and recursively apply InnerEndpointsReduce using u′u' as the neighbor of the new start uu.

Proof (Lemma 7). Let PP be an stst-path with both endpoints on the inner layer. Let s′∈L1s' \in L_1 be a cyclic neighbor of ss that does not share an edge with ss, and assume s′=ccw⁡(s)s'=\operatorname{ccw}(s) by symmetry.

In the first three cases we try to create a new level edge between ss and s′s'.

  • Case 1: If ss does not see s′s', then ObstrReduction reduces the potential in O(1)O(1) according to Lemma 8.

  • Case 2: If ss sees s′s' and the incoming edge of s′s' is a non level edge, then flipping it to ss′ss' instantly decreases the potential.

  • Case 3: If ss sees s′s' and s′=ts'=t is the end, then we can pick any non level edge and flip it to ss′ss' to decrease the potential.

So now, suppose that ss sees s′s', and the incoming edge of s′≠ts' \ne t is a level edge. Cases 4-6 follow different strategies depending on the type of out⁡(s′)\operatorname{out}(s').

  • Case 4: If out⁡(s′)\operatorname{out}(s') is a small diagonal, the idea is that we can rotate that diagonal, with x=succ⁡(s′)x=\operatorname{succ}(s') as an anchor, via the flips s′x→sxs'x \to sx followed by in⁡(s)→s′s\operatorname{in}(s) \to s's. We repeat applying this case until a level edge is created as illustrated in Figure 8. The validity of the sequence comes from two loop invariants:

    • s,s′∈L1s,s' \in L_1 are neighbors and see each other;

    • s′xs'x is a small diagonal with x=succ⁡(s′)x=\operatorname{succ}(s'),

Rotation of a small diagonal

Figure 8. Rotation of a small diagonal in O(n1)O(n_1) flips until the potential decreases.

and the termination is implied by the fact that after an iteration of the loop, the couple (s,s′)(s,s') is shifted clockwise, so if the loop does not stop earlier, the diagonal s′xs'x will rotate until it becomes a level edge, when s′s' becomes ccw⁡(x)\operatorname{ccw}(x). This loop can rotate that diagonal at most O(n1)O(n_1) times, meaning that the reduction step in this case takes O(n1)O(n_1) flips.

– Case 5: If out⁡(s′)\operatorname{out}(s') is a medium diagonal, the idea is to use first rotate the diagonal until the potential diminishes as illustrated in Figure 9, or x=succ⁡(s′)x=\operatorname{succ}(s') does not see ss (Case 5.(a)), and then if the potential has not already be diminished, use the procedure DiagObstrReduction on the obstruction between ss and xx (Case 5.(b)).

Rotation of a medium diagonal

Figure 9. Rotation of a medium diagonal in Case 5.(a) of InnerReduction in O(n1)O(n_1) flips.

The proof for the validity of Case 5.(a) is similar to Case 4, so let’s focus on Case 5.(b). If ss does not see xx, and tt is on the other side of the medium diagonal, we can show that the path verifies the premises of Lemma 9. Let u=s′u=s' and v=xv=x. Then since vv does not see ss, the path must enter the triangle △suv\triangle suv without crossing uvuv (planarity) or susu (assumption). Thus the existance of an inner point p∈△suvp \in\triangle suv the closest to uvuv. Then we can prove that pp sees ss and vv.

Also, we can observe that the prefix P[s:u]P[s:u] must contain an outer point. Let u′∈L0u' \in L_0 be the last one of that prefix. Then the idea is that P[v:u′]P[v:u'] separates the set of point in 2 parts, and the prefix must visit all the points of it’s left side. With this observation and the fact that ss sees uu, we can deduce that the path cannot visit any outer point before reaching pp without crossings. And similar planarity restrictions enforce the prefix P[s:p]P[s:p] to visit a subset of points of L1L_1 in clockwise order, and the subpath P[p:u′]P[p:u'] to contain at least all the points of L0L_0 between v′=ccw⁡(v)v'=\operatorname{ccw}(v) and u′u' in counterclockwise order. Therefore the premises of DiagObstrReduction are met and it can reduce the potential in O(1)O(1) flips. An example of a path in this case is given in Figure 10.

Prefix structure of the path in Case 5.(b) of InnerReduction

Figure 10. Prefix structure of the path in Case 5.(b) of InnerReduction

  • Case 6: If out⁡(s′)\operatorname{out}(s') is a bridge, the natural goal is to remove it. We subdivise that case since the path can have different properties depending on the shape of the prefix.

  • Case 6.(a): If P[s:s′]⊄L1P[s:s'] \not\subset L_1 To enforce stong properties on the path, suppose s′,u=succ⁡(s′)s', u = \operatorname{succ}(s') and succ⁡(u)\operatorname{succ}(u) are in clockwise order (otherwise we can come back to this case with a single flip). Then let xx be the first outer point visited by the path. Then we can show that the polygonal line formed by us′us' and P[s:x]P[s:x] splits the points in half, with the suffix P[u:t]P[u:t] on the left side, and the subpath P[x:s′]P[x:s'] on the left as illustrated in Figure 11. We can deduce from this structure that the prefix P[s:u]P[s:u] must visit every outer point from xx to uu in clockwise order. So the last outer point visited before uu was v=ccw⁡(u)v = \operatorname{ccw}(u). Let v′=succ⁡(v)v' = \operatorname{succ}(v). If ss sees v′v' (Case 6.(a).i), then the flip vv′→sv′vv' \to sv' transforms a bridge or medium diagonal into a small diagonal, and s′u→vus'u \to vu creates a level edge on the L0L_0 as illustrated in Figure 12

Illustration of the dashed polygonal line separating the points in two parts in Case 6.(a) of InnerReduction

Figure 11. Illustration of the dashed polygonal line separating the points in two parts in Case 6.(a) of InnerReduction

Reduction of the potential in Case 6.(a).ii of InnerReduction

Figure 12. Reduction of the potential in Case 6.(a).ii of InnerReduction

Otherwise (Case 6.(a).ii), there must be a small diagonal in P[v′:s′]P[v':s'] blocking the vision between ss and vv. Let pqpq be the last small diagonal of that subpath. Then P[q:s′]P[q:s'] only contains level edges and ss sees s′s' so the flip pq→sqpq \to sq is valid and does not change the potential.

Now, let’s show that applying the same procedure on the new path does not make a loop. Let p′=ccw⁡(p)p' = \operatorname{ccw}(p). That point does not share an edge with pp because otherwise P[v′:p′]P[v':p'] would have had to cross pqpq. Therefore when applying this procedure, the choice of p′p' for the neighbor of the start pp of the new path P′P' is valid, and we can show that in P′P', if the incoming edge of p′p' is a level edge, its outgoing edge is a bridge and it sees pp, then that bridge must be crossing the subpath P′[p:p′]P'[p:p']. Therefore Case 6 cannot be applied again in P′P', so one of the other ones will. So in the worst case, the potential will be diminished in O(n1)O(n_1) flips. An illustration of that case is presented in Figure 13.

Reduction from Case 6.(a).ii to other cases of InnerReduction

Figure 13. Reduction from Case 6.(a).ii to other cases of InnerReduction.

  • Case 6.(b) Otherwise P[s:s′]⊂L1P[s:s'] \subset L_1. In this last case, there is no immediate reduction possible in the general case, so we perform a flip to reduce that case to the other ones. Let uvuv be the first small diagonal of P[s:s′]P[s:s']. It must exist as t∈L1t \in L_1 is not in P[s:s′]P[s:s']. Then uu has neighbor u′u' not seen by ss, and u′u' cannot be connected to uu because otherwise P[u′:s′]P[u':s'] would need to cross uvuv. So after the flip uv→svuv \to sv, uu becomes the start of the new path P′P' and u′u' is a valid choice for the neighbor of uu in the recursive call of the procedure for P′P'. Also, we can be sure that P′P' will not fall again into Case 6.(b) since u∉P[s:s′]u \notin P[s:s'], so u∉P′[u:s′]u \notin P'[u:s'] and therefore P′[u:u′]⊄L1P'[u:u'] \not\subset L_1. So in the worst case, the potential will be diminished in O(n1)O(n_1) flips. This reduction of case is represented in Figure 14.

Figure 14. Reduction from Case 6.(b) to other cases of InnerReduction.

Therefore each case uses at most O(n1)O(n_1) flips to reduce the potential.

Obstruction procedures and proof of Lemmas 8 and 9

Procedure ObstrReduction.

Input: a path PP whose start s∈L1s \in L_1 does not see one of its neighbor q∈L1q \in L_1. Assume q=ccw⁡(s)q = \operatorname{ccw}(s) by symmetry. Let uvuv be the closest edge to ss intersecting sqsq, with u=pred⁡(v)u = \operatorname{pred}(v).

  1. If vv sees ss, perform uv⟶svuv \longrightarrow sv.

  2. Else follow the procedure DiagObstrReduction.

Procedure DiagObstrReduction. Input: A path PP starting at s∈L1s \in L_1 such that there is a medium or big diagonal uvuv, with v∈L0v \in L_0, intersecting the convex hull of the inner layer next to ss and another vertex pp. Suppose also that pp is inside the triangle △suv\triangle suv, and that the prefix P[s:p]P[s:p] visits a subset of L1L_1 in circular order from ss to pp, and the subpath P[p:u′]P[p:u'] visits all the points between ss and pp skipped by the prefix (without particular order), and all the outer points in order from v′v' (the first neighbor of vv visited by after pp) to u′u' (the last outer point visited before uu).

Suppose without loss of generality that the crossing of the diagonal uvuv is counterclockwise to ss. Let s′=pred⁡(p)s' = \operatorname{pred}(p), v′=ccw⁡(v)v' = \operatorname{ccw}(v) and p′=ccw⁡(p)p' = \operatorname{ccw}(p).

  1. If succ⁡(p)∈L1\operatorname{succ}(p) \in L_1, perform

s′p→sp,psucc⁡(p)→s′succ⁡(p),uv→pv.s'p \to sp,\qquad p\operatorname{succ}(p) \to s'\operatorname{succ}(p),\qquad uv \to pv.
  1. Else if p′∈P[s:p]p' \in P[s:p], perform

s′p→sp,pv′→s′v′,uv→pv.s'p \to sp,\qquad pv' \to s'v',\qquad uv \to pv.
  1. Else if p′p' does not see pp:

Let abab, with b=succ⁡(a)b = \operatorname{succ}(a), be the closest edge intersecting pp′pp' and perform

s′p→sp,ab→s′b.s'p \to sp,\qquad ab \to s'b.
  1. Otherwise, perform

s′p→sp.s'p \to sp.

(a) If succ⁡(p′)∈L1\operatorname{succ}(p') \in L_1, let y=succ⁡(p′)y = \operatorname{succ}(p') and perform

p′y→s′y,v′p→p′p,uv→vv′.p'y \to s'y,\qquad v'p \to p'p,\qquad uv \to vv'.

(b) Else if pred⁡(p′),succ⁡(p′)∈L0\operatorname{pred}(p'),\operatorname{succ}(p') \in L_0,

Let x=pred⁡(p′)x = \operatorname{pred}(p') and y=succ⁡(p′)y = \operatorname{succ}(p') and perform

xp′→s′p′,p′y→xy.xp' \to s'p',\qquad p'y \to xy.

(c) Otherwise, succ⁡(p′)∈L0\operatorname{succ}(p') \in L_0 and pred⁡(p′)∈L1\operatorname{pred}(p') \in L_1.

i. if s′s' does not see cw⁡(s′)\operatorname{cw}(s'), recursively apply DiagObstrReduction on the obstruction between s′s' and cw⁡(s′)\operatorname{cw}(s').

ii. Else if the incoming edge of cw⁡(s′)\operatorname{cw}(s') is not level, perform

in⁡(cw⁡(s′))→s′cw⁡(s′).\operatorname{in}(\operatorname{cw}(s')) \to s'\operatorname{cw}(s').

iii. Otherwise, perform

in⁡(cw⁡(s′))→s′cw⁡(s′),in⁡(p′)→p′cw⁡(cw⁡(s′)).\operatorname{in}(\operatorname{cw}(s')) \to s'\operatorname{cw}(s'),\qquad\operatorname{in}(p') \to p'\operatorname{cw}(\operatorname{cw}(s')).

Proof (Lemma 8). Let PP be an stst-path whose start s∈L1s \in L_1 does not see one of its neighbor qq, and assume q=ccw⁡(s)q = \operatorname{ccw}(s) by symmetry. Let uvuv be the closest edge to ss intersecting sqsq. Then uvuv is either a medium diagonal or a big diagonal, so it has a lot of weight. Therefore the goal is to remove it. We can observe that because of the definition of uvuv, ss sees either uu or vv.

  • Case 1. If ss sees vv, then the flip uv→svuv \to sv is legal and we can show by case exhaustion that no matter the type of uvuv initially, that flip decreases the potential. The different subcases are illustrated in Figure 15.

Three cases illustrating immediate potential reduction

Figure 15. (a) vv is an inner point; (b) vv is an outer point next to ss; (c) vv is an outer point far from ss. Immediate potential reduction in case 1 of ObstrReduction

  • Case 2. Otherwise, ss does not see vv but ss sees uu, so we can deduce that the diagonal uvuv must be a big diagonal, otherwise, ss would have been able to see vv. We can now show that the path has the strong structural properties that enable the use of the procedure DiagObstrReduction.

Since ss does not see vv, the path must enter the triangle △suv\triangle suv without crossing uvuv (planarity) or susu (assumption). so that triangle contains at least 1 point of L1L_1 inside of it. Let pp be the closest point to uvuv inside that triangle. Then we can prove that there is no other point inside the concave quadrilateral suvpsuvp or that would contradict the definition of pp, therefore pp sees both ss and vv.

Now, since uvuv is a big diagonal, it splits the point set in two parts, and in particular, it must separate the start ss from the end tt because otherwise an entire side could not be visited without crossings. This means that the prefix P[s:u]P[s:u] must visit the entire left side of uvuv. Moreover, since the quadrilateral suvpsuvp cannot be crossed by the path, we can deduce that the prefix P[s:p]P[s:p] cannot visit any point of L0L_0 without introducing crossings or violating the definition of uvuv or pp. Therefore P[p:u]P[p:u] must visit at least all the outer points from ccw⁡(v)\operatorname{ccw}(v) to uu. With the same argument, we can observe that P[s:p]P[s:p] must visit that subset of L1L_1 in clockwise order and all the outer points of the left side are visited in counterclockwise order in P[p:u]P[p:u]. The structure of the prefix of that path is illustrated in Figure 16.

Illustration of the particular prefix the path has in Case 2 of ObstrReduction

Figure 16. Illustration of the particular prefix the path has in Case 2 of ObstrReduction to constrain the shape of the path until it forces the appearance of a medium diagonal in the prefix that is easy to remove.

Therefore the premises of the procedure DiagObstrReduction are met and it can reduce the potential in O(1)O(1) flips.

Therefore in both cases, the potential of the path can be reduced in O(1)O(1) flips. □\square

Proof (Lemma 9). The main goal of this procedure is to remove the diagonal uvuv by flipping it to pvpv, or to remove any other heavy weight edge encountered in the prefix. This procedure does it by successively eliminating simple cases.

Let s′=pred⁡(p)s' = \operatorname{pred}(p). A first easy case is when the successor of pp is an inner point.

– Case 1. If succ⁡(p)∈L1\operatorname{succ}(p) \in L_1, we can make pp the new starting point with 2 flips: s′p→sps'p \to sp followed by psucc⁡(p)→s′succ⁡(p)p\operatorname{succ}(p) \to s'\operatorname{succ}(p). These flips are legal since pp sees ss and s′psucc⁡(p)s'p\operatorname{succ}(p) is an empty triangle of L1L_1 where two of the borders cannot be crossed by planarity, so s′s' sees succ⁡(p)\operatorname{succ}(p). After these two flips, the potential may have increased by 1 at most. However, the last flip uv→pvuv \to pv transform a medium or big diagonal into a bridge, diminishing the potential by at least 2. So at the end of that sequence, the potential has decreased by at least 1. This flip sequence is illustrated in Figure 17

Reduction of potential in Case 1 of DiagObstrReduce

Figure 17. Reduction of potential in Case 1 of DiagObstrReduce

Suppose now that succ⁡(p)∈L0\operatorname{succ}(p) \in L_0. Since by assumption the subpath P[p:u]P[p:u] visits all the outer points from v′=ccw⁡(v)v' = \operatorname{ccw}(v) to uu in counterclockwise order, we can deduce that succ⁡(p)=v\operatorname{succ}(p) = v. Let p′=ccw⁡(p)p' = \operatorname{ccw}(p). The case analysis is now refined based on the position of p′p' in the path

– Case 2. If p′∈P[s:p]p' \in P[s:p], then p′=s′p' = s' since by assumption on P[s:p]P[s:p], that prefix visit points of L1L_1 in clockwise order. The sequence of flips we perform in this case is the same as in Case 1, except this time the second flip is legal because v′v' and p′p' see each other. Indeed, if that was not the case, the convexity of L1L_1 would prevent the quadrilateral suvpsuvp from being concave, which would mean that ss would see vv, contradicting the assumption made on the initial path.

So at the end of that sequence (illustrated in Figure 18, the potential has decreased by at least 1 in O(1)O(1) flips.

Reduction of potential in Case 2 of DiagObstrReduction

Figure 18. Reduction of potential in Case 2 of DiagObstrReduction

  • Case 3. If p′∉P[s:p]p' \notin P[s:p] and p′p' does not see pp, then there is a medium diagonal blocking the view between those points. Let abab be the closest edge to pp intersecting pp′pp'. Then we can show that necessarily a∈L0a \in L_0 and b∈L1b \in L_1, otherwise there would need to be some crossings in the path. We can also show that s′s' sees bb since the triangle △s′pb\triangle s'pb is empty and the path cannot cross s′ps'p (planarity) nor can it cross bpbp (definition of abab). So after the first neutral flip s′p→sps'p \to sp, the flip ab→s′bab \to s'b reduced the potential by at least 2 as illustrated in Figure 19.

Reduction of potential in Case 3 of DiagObstrReduction

Figure 19. Reduction of potential in Case 3 of DiagObstrReduction.

Now suppose p′p' sees pp and p′∉P[s:p]p' \notin P[s:p] (Case 4.), i.e. p′∈P[v′:u]p' \in P[v':u]. Then like all the previous cases, we start flipping s′p→sps'p \to sp to form a new path P′P' as illustrated in Figure 20. In this case, we know that s′s' is not a cyclic neighbor of pp in the path, so s′ps'p is a small diagonal, just like spsp. Therefore Φ(P)=Φ(P′)\Phi(P)=\Phi(P').

The original path $P$ and the new path $P'$

Figure 20. First flip of Case 4 of DiagObstrReduction.

We refine again the case analysis based on the position of the predecessor and the successor of p′p'. We can observe that 2 cases can be solved easily.

  • Case 4.(a): If succ⁡(p′)∈L1\operatorname{succ}(p') \in L_1, This case resembles the flip sequence from Case 1: with the same empty triangles arguments we can deduce the required visibility to prove that all the flips performed in this case are legal. The potential could stay the same after the first 2 flips but decreases by at least 3 with the last one as illustrated in Figure 21.

Reduction of potential in Case 4.(a)

Figure 21. Reduction of potential in Case 4.(a) of DiagObstrReduction.

  • Case 4.(b) If succ⁡(p′)∈L0\operatorname{succ}(p') \in L_0 and pred⁡(p′)∈L0\operatorname{pred}(p') \in L_0, then by the assumption on the path, we know that x=pred⁡(p′)x=\operatorname{pred}(p') is the clockwise neighbor of y=succ⁡(p′)y=\operatorname{succ}(p'). In this case we can just connect them in 2 flips. By the same empty triangle argument we know that s′s' sees p′p', and since they are outer layer neighbor, we know that xx sees yy, thus the validity of both flips. Moreover, that sequence

of flips transforms two bridges into a level edge and a small diagonal, so the potential decreases by 1 as illustrated in Figure 22.

Reduction of potential in Case 4.(b) of DiagObstrReduction

Figure 22. Reduction of potential in Case 4.(b) of DiagObstrReduction.

Now suppose succ⁡(p′)∈L0\operatorname{succ}(p') \in L_0 and pred⁡(p′)∈L1\operatorname{pred}(p') \in L_1. In this case, the outgoing edge of p′p' is so constrained that it is forced to be a medium diagonal as we will show in the relevant subcase. Therefore, we shift the objective from flipping uvuv to flipping out⁡(p′)\operatorname{out}(p'). However, the edge is in the wrong direction to be flipped directly. Therefore we use cw⁡(s′)\operatorname{cw}(s') to change the orientation of that edge to flip it (Case 4.(c).iii), if the potential cannot be reduced immediately (Case 4.(c).i-ii).

  • Case 4.(c).i If s′s' does not see cw⁡(s′)\operatorname{cw}(s'), because of the structure of the prefix assumed in the hypotheses of the lemma, that blocking edge cannot be a big diagonal, therefore it is a medium one, so applying procedure ObstructionReduce will reduce the potential with its case 1 in 1 flip.

  • Case 4.(c).ii If s′s' sees cw⁡(s′)\operatorname{cw}(s') and in⁡(cw⁡(s′))\operatorname{in}(\operatorname{cw}(s')) is not a level edge, then the flip in⁡(cw⁡(s′))→s′cw⁡(s′)\operatorname{in}(\operatorname{cw}(s')) \to s'\operatorname{cw}(s') creates a level edge, reducing the potential.

  • Case 4.(c).iii if s′s' sees cw⁡(s′)\operatorname{cw}(s') and in⁡(cw⁡(s′))\operatorname{in}(\operatorname{cw}(s')) is a level edge, then the flip in⁡(cw⁡(s′))→s′cw⁡(s′)\operatorname{in}(\operatorname{cw}(s')) \to s'\operatorname{cw}(s') makes cw⁡(cw⁡(s′))\operatorname{cw}(\operatorname{cw}(s')) the new start, and reverses the order of the path in P′P' [s′:cw⁡(s′)][s' : \operatorname{cw}(s')] as displayed in Figure 23.

Reduction of potential in Case 4.(c).iii of DiagObstrReduction

Figure 23. Reduction of potential in Case 4.(c).iii of DiagObstrReduction.

The second flip is valid since after the first flip, p′p' sees s′s' which is connected to cw⁡(s′)\operatorname{cw}(s') which sees cw⁡(cw⁡(s′))\operatorname{cw}(\operatorname{cw}(s')), and all these points form an empty quadrilateral, so pp sees cw⁡(cw⁡(s′))\operatorname{cw}(\operatorname{cw}(s')).

Now to prove that the potential reduces, we must prove that in P′P', the outgoing edge of p′p' is a medium diagonal, and that after the first flip, the order of the path in p′p' is reversed, meaning that that medium diagonal is flipped for a small one in the second flip.

Since p′∈L1p' \in L_1 and succ⁡(p′)∈L0\operatorname{succ}(p') \in L_0, the outgoing edge of p′p' is either a bridge or a medium diagonal. Suppose for contradiction that it is a bridge, and consider the simple loop Γ=vp∪pp′∪p′succ⁡(p′)∪γv,succ⁡(p′)\Gamma= vp \cup pp' \cup p'\operatorname{succ}(p') \cup\gamma_{v,\operatorname{succ}(p')} where γv,succ⁡(p′)\gamma_{v,\operatorname{succ}(p')} lies outside conv⁡(S)\operatorname{conv}(S) except at its endpoints vv and succ⁡(p′)\operatorname{succ}(p'). By the Jordan curve theorem, Γ\Gamma separates the plane into two regions. Since p′succ⁡(p′)p'\operatorname{succ}(p') is a bridge and p′p' is a neighbor of pp, the region containing v′=ccw⁡(v)v'=\operatorname{ccw}(v) contains no point of L1L_1 other than pp and p′p' at its border, so in particular, it does not contain pred⁡(p′)\operatorname{pred}(p'). Therefore P′[pred⁡(p′):pred⁡(p′)]P'[\operatorname{pred}(p') : \operatorname{pred}(p')] must cross Γ\Gamma, but it cannot cross vpvp and pp′pp' (assumption), it cannot cross p′succ⁡(p′)p'\operatorname{succ}(p') (planarity) and it cannot cross γv,succ⁡(p′)\gamma_{v,\operatorname{succ}(p')} (outside the hull). This contradiction shows that out⁡(p′)\operatorname{out}(p') is a medium diagonal.

We can also show with a different loop that p′p' must be visited before cw⁡(s′)\operatorname{cw}(s') in P′P', therefore after the first flip, the medium diagonal of p′p' becomes its incoming edge and the potential diminishes by at least 2 in the second flip.

So in any case, the potential diminishes by at least 1 in O(1)O(1) flips. □\square

Proof of Lemma 5

Using Lemma 4 alone, we would get a flip complexity of O(n1(n0+n1))O(n_1(n_0+n_1)) in the worst case. In this section we prove that the expensive cases where we may need Ω(n1)\Omega(n_1) flips in a reduction step does not happen too often. In fact, we show that at most O(n1)O(n_1) reduction steps may need strictly more than 1 flip to be performed.

First, we can observe that the number of bridges B(P)B(P), the number of small diagonals S(P)S(P), and the number of medium diagonals M(P)M(P) are all bounded by 2n12n_1 as these edge types all have an extremity in L1L_1. Therefore, we just need to show that most of the big diagonals can be removed in 1 flip throughout the reduction process.

Let I\mathcal{I} be the set of boundary segments of conv⁡(L1)\operatorname{conv}(L_1) induced by the vertices of L1L_1.

Let PP be a path. For A,B∈IA,B\in\mathcal{I}, let GP(A,B)G_P(A,B) denote the set of big diagonals whose two intersections with conv⁡(L1)\operatorname{conv}(L_1) belong respectively to the intervals AA and BB. We also denote by GP(∅)G_P(\varnothing) the set of big diagonals that do not intersect conv⁡(L1)\operatorname{conv}(L_1), so that GP(∅)∪⋃A,B∈IGP(A,B)G_P(\varnothing)\cup\bigcup_{A,B\in\mathcal{I}}G_P(A,B) forms a partition of the set of big diagonals of PP. Because of the planarity of the path, the support of that partition is O(n1)O(n_1) (Lemma 10).

Lemma 10. For any given path PP, the number of non-empty sets GP(A,B)G_P(A,B) is O(n1)O(n_1).

Proof. Associate to each non-empty set a representative big diagonal. Since big diagonals of a plane path are pairwise non-crossing, these representatives form a family of non-crossing chords of dual of the convex polygon conv⁡(L1)\operatorname{conv}(L_1).

The graph whose vertices are the segments of conv⁡(L1)\operatorname{conv}(L_1) (i.e. I\mathcal{I}) and whose edges correspond to non-empty sets is therefore outerplanar. Since ∣I∣=n1|\mathcal{I}|=n_1, it contains only O(n1)O(n_1) edges. Hence only O(n1)O(n_1) sets are non-empty.

This partition of the big diagonals enables the following observation.

Observation 11. Let PP be a path. As soon as one big diagonal of G∈{GP(∅)}∪{GP(A,B),A,B∈I}G \in\{G_P(\emptyset)\} \cup\{G_P(A,B), A,B \in\mathcal{I}\} has been flipped, we can transform every remaining diagonal of GG to level edges using one flip per diagonal.

Proof. Suppose G=GP(A,B)≠∅G=G_P(A,B)\ne\emptyset, for A,B∈IA,B\in\mathcal{I}, and suppose we are about to flip one diagonal of GG. We can order them by the order in which they appear in the path (that would correspond to left-to-right or right-to-left if they were vertical). Let uvuv be the first and xyxy be last diagonal of GG.

Since each big diagonal separates the point set in two parts, we can deduce that they also separate the endpoints (planarity and Hamiltonicity). Applying this principle on uvuv and xyxy, we can deduce that there is no endpoint in the region of the plane between the lines uvuv and xyxy. So no other diagonal from GG can be visible by the endpoints, therefore, by symmetry we can suppose that uvuv is the diagonal we are about to flip, and that uu will become the next starting point.

By definition of GP(A,B)G_P(A,B), there is no inner point in the region between the lines uvuv and xyxy, so the vertices of the subpath P[u:y]P[u:y] are in convex position. This forces a particular structure where each successive diagonal are connected by level edges, and as soon as uvuv has been flipped, so that uu becomes an endpoint, we can successively flip all the diagonals in order to level edges like in the convex case.

The proof is the similar when G=GP(∅)G=G_P(\emptyset). ⊓⊔

Therefore, according to Observation 11, at most 1+∣GP(A,B)≠∅∣=O(n1)1+|G_P(A,B)\ne\emptyset|=O(n_1) big diagonals may need more than 1 flip in the reconfiguration process. We can now prove Lemma 5.

Proof (Lemma 5). According to Observation 11, at most B(P)+S(P)+3M(P)+4(1+∣GP(A,B)≠∅∣)=O(n1)B(P)+S(P)+3M(P)+4(1+|G_P(A,B)\ne\emptyset|)=O(n_1) reduction steps may require more than 1 flip. ⊓⊔

Acknowledgments and Disclosure of Interests. Use of AI: Generative AI tools were used for literature search, language polishing, manuscript formatting, and improving the exposition of the paper. They were also used as an auxiliary aid to review the presentation of proofs and identify possible inconsistencies. Generative AI tools were not used to generate the scientific results, proofs, algorithms, or conclusions of this work. All AI-assisted content was reviewed and verified by the authors, who take full responsibility for the final manuscript. The authors have no competing interests to declare that are relevant to the content of this article.

References

  1. [1]Aichholzer, O., Dorfer, J.: A linear time algorithm for the flip distance between plane spanning paths in convex point sets. Comput. Geom. Topol. 5, 2:1–2:17 (2026)DOI
  2. [2]Aichholzer, O., Knorr, K., Mulzer, W., Obenaus, J., Paul, R., Vogtenhuber, B.: Flipping plane spanning paths. In: Proc. 17th Int. Conf. Workshops Algorithms Comput. (WALCOM). LNCS, vol. 13973, pp. 49–60 (2023)arxiv.org/abs/2202.10831
  3. [3]Akl, S.G., Islam, M.K., Meijer, H.: On planar path transformation. Inf. Process. Lett. 104, 59–64 (2007)
  4. [4]Boucard, V., da Fonseca, G.D., Rivier, B.: Further connectivity results on plane spanning path reconfiguration. arXiv:2407.00244 (2024)arxiv.org/abs/2407.00244
  5. [5]Chang, J.M., Wu, R.Y.: On the diameter of geometric path graphs of points in convex position. Inf. Process. Lett. 109, 409–413 (2009)DOI
  6. [6]Kleist, L., Kramer, P., Rieck, C.: On the connectivity of the flip graph of plane spanning paths. In: Proc. 50th Int. Workshop Graph-Theoretic Concepts Comput. Sci. (WG). LNCS, vol. 14760, pp. 327–342 (2025)arxiv.org/abs/2407.03912
  7. [7]Rivera-Campo, E., Urrutia-Galicia, V.: Hamilton cycles in the path graph of a set of points in convex position. Comput. Geom. 18, 65–72 (2001)DOI

Paper details

vlnc:W_hqcvwpjx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents