WorksComputer Science
Quadratic Reconfiguration of Plane Spanning Paths on Two-Layer Point Sets
Abstract
Consider a crossing-free polygonal path with 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 flips suffice. More precisely, for a two-layer point set , where and denote the outer and inner layers, respectively, our method uses 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 of points and the flip operation removes an edge and adds another one while preserving a valid configuration. Given a set , 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 in convex position ( is the set of convex hull vertices). The first polynomial bound on the diameter for the convex case appears in [3], at most . Later a tight bound of for and for 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 [2]. For convex position plus one exterior point, the diameter is at most [4]. Both cases are special cases of a more general two-layer point set where the outer layer is the set of vertices in the convex hull of and the inner layer 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 , where and denote the outer and inner layers, the diameter of the flip graph is and computing a flip sequence connecting a pair of paths takes time.
Canonical Paths and Potential Reduction
This section assembles the main elements allowing us to prove Theorem 1. Let be a two-layer point set with and the outer and inner layer respectively. Let and .
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 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 , in a path , we say that sees if the interior of the segment does not intersect any other edge of .
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 -path is an oriented path with start and end . For a vertex , we denote by and its incoming and outgoing edges, when they exist. We write and for the predecessor and successor of , respectively. Whenever an edge is written as in an oriented path, we implicitly assume that .
For an -path , the subpath from to is denoted by . A prefix of the path is any subpath of the form , , and a suffix of the path is any path of the form , .
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.

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 flips.
Proof. Let and be two canonical paths with bridges and , where and .
Consider a triangulation of the ring between and that contains both and and such that and no triangle connects three points of . In such a triangulation, the edges joining and form a cyclic sequence 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 and to and respectively.
Starting from , repeatedly flip the bridge to the next one of 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 into . 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 .
At the end of that loop we can correct the orientation of the path at the extremity of the bridge to match in 2 flips. Therefore can be transformed into .
Moreover, the sequence contains exactly edges. So the whole process uses at most flips, proving the claim.
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 ;
small diagonals, joining two non-consecutive vertices of ;
medium diagonals, joining an outer and an inner vertex through the interior of the convex hull of ;
big diagonals, joining two non-consecutive vertices of .
These edge types are represented in Figure 3.

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 of a path as
where , , , and denote the numbers of level edges, bridges, small diagonals, medium diagonals and big diagonals in , 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 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 for every path .
Now let be a path with . Since every edge type except level edges has weight at least 1, the path must contain exactly one bridge and all its remaining edges must be level edges.
Consequently, the restriction of to contains exactly level edges and the restriction of to contains exactly level edges. Hence the vertices of each layer are traversed consecutively in cyclic order. The unique bridge connects the two layer-traversals, so is a canonical path.
Conversely, every canonical path consists of a single bridge and level edges, and therefore has potential 1.
Lemma 4. If a path is not canonical, we can reduce its potential by at least 1 with a sequence of at most flips.
Lemma 5. Throughout the process of diminishing the potential of the path, at most potential reduction steps require more than 1 flip.
These last two lemmas enable the proof of Theorem 1.
Proof (Theorem 1). Let be a path. By Lemma 4, we can diminish its potential in at most flips, until it has least potential and becomes canonical (Lemma 3). Among each of these reduction steps, at most of them may require more than 1 flip to be performed, according to Lemma 5. Therefore, since , this means that the reconfiguration of into a canonical path requires at most .
Moreover, using Lemma 2, we can reconfigure any canonical paths into one another in flip, meaning we can reconfigure any path into one another in flips.
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

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 with , performs a sequence of flips that decreases the potential. The algorithm uses two different procedures, depending on whether an endpoint of 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 be an -path where the start is an outerpoint. Then the procedure OuterReduction reduces the potential of the path in 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 flips in certain cases.
Lemma 7. Let be an -path where both endpoints are in . Then the procedure InnerReduction reduces the potential of the path in 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 be a path starting at and let be a neighbor not seen by because some edge of blocks the visibility between them. Then the procedure ObstrReduction reduces the potential of the path in flips.
Lemma 9. Let be a path starting at . Suppose that contains a diagonal , where either is a big diagonal or is a medium diagonal with a cyclic neighbor of in . Assume that sees but not , and that there exists an inner vertex that sees both and . Moreover, assume that the concave quadrilateral is empty.
Let be the last outer vertex on and let be the first neighbor of visited by . Assume further that
lies entirely in and visits its vertices in cyclic order from to ;
and visits the remaining inner vertices between and , together with the outer vertices from to , preserving their cyclic order on .
Then DiagObstrReduction reduces the potential of using 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 whose start lies on the outer layer, and a neighbor of that does not share an edge with it. Assume by symmetry. Let be the end of the path.
If , pick any non-level edge and flip it to .
Else if the incoming edge of is not a level edge, flip it to .
Otherwise: Let be a neighbor of that does not share an edge with it. (a) If does not see , reverse the order of the path and apply the ObstrReduction procedure on that obstruction. (b) Else if the outgoing edge of is not a level edge, flip it to . (c) Else if , perform
(d) Otherwise, let , with , be the last small diagonal in , and let be neighbor of not seen by . Then perform , and apply recursively OuterReduction using for the non connected neighbor of the new start .
Proof (Lemma 6). Let be an -path starting at , and assume , otherwise the lemma is trivial. Let be one of the cyclic neighbor of and assume 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 is a level edge. Then the path has a particular structure. Indeed, as illustrated in Figure 5, the prefix wraps around the suffix so that the latter is forced to stay confined in . In particular, the end is an inner point. This restriction on the suffix means that must visit all outer points, and we can prove that all the points from must appear in a cyclic order in that prefix.

Figure 5. Structure of the path in Case 3 of procedure OuterReduction
Also, since the incoming edge of is a level edge, its outgoing edge is not as does not share an edge with . So the remaining cases try to reverse the orientation of the path in if it cannot be immediately be reduced near .
Let be a neighbor of such that does not share an edge with . Such a always exists unless and the path already has potential 1. We distinguish cases depending on visibility between and and the type of the outgoing edge of .
Case 3.(a): If does not see , then applying ObstrReduction reduces the potential in according to Lemma 8.
Case 3.(b): If sees and the outgoing edge of is not a level edge, then creates a new level edge, diminishing the potential.
Now let’s suppose that sees , and is a level edge.
Case 3.(c): If or equivalently , the first flip is legal and does not change the potential. The second flip is also legal as sees . Moreover, after the first flip the orientation of the path in is reversed, exchanging with the non-level edge . 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.

Figure 6. Reduction of potential in Case 3.(c) of Procedure OuterReduction.
Case 3.(d): Suppose . In this case, we can show that . Indeed, if that was not the case, then as and is a level edge, must be a small diagonal. This diagonal would cut in two parts, separating and the two neighbors of and introducing a crossing with the suffix . Therefore in this case .
From this observation we can deduce that necessarily contains a small diagonal, as if it was not the case, would visit all inner points in cyclic order, which would imply that the path is already canonical. Now, as in the procedure, let be the last diagonal of . Then it splits in half and we can define to be the neighbor of not seen by . The flip does not necessarily decrease the potential, but it changes the end of the path to , so that applying again the procedure with for the choice of the neighbor of will not lead to that case again, since so . And since all the other cases decrease the potential in flips, this one does as well. The flip sequence produced in this case is illustrated in Figure 7.

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 flips.
Procedure InnerReduction and proof of Lemma 7
Procedure InnerEndpointsReduce. Input: a path whose start and end lie on the inner layer, and a neighbor of that does not share an edge with it. Assume by symmetry.
If does not see , apply the ObstrReduction procedure on that obstruction.
Else if the incoming edge of is not a level edge, flip it to .
Else if , pick any non-level edge and flip it to .
Else if the outgoing edge of is a small diagonal: Let . Repeat until the potential decreases: let be the start of the path, and , and perform
Else if the outgoing edge of is a medium diagonal: Let . If and are on the same side of in , flip , rename as , and take the reflect the path so that again. Then (a) If sees , repeat until the potential decreases or no longer sees : let be the start of the path, and , and perform
If the potential has not decreased, then follow the procedure DiagObstrReduction with the start and diagonal . (b) If does not see , follow the procedure DiagObstrReduction with the start and diagonal .
Otherwise, the outgoing edge of is a bridge.
(a) If , Let . If , , are not in clockwise order, flip to , rename as , and reflect the path so that becomes again, and the order of , , becomes clockwise. Let and .
i. If sees , perform , then .
ii. Else let be the last small diagonal of , with , and let . Then flip and recursively apply InnerEndpointsReduce using as the neighbor of the new start .
(b) Otherwise . Let be the first small diagonal of , with . let be the neighbor of not seen by . Then flip to , and recursively apply InnerEndpointsReduce using as the neighbor of the new start .
Proof (Lemma 7). Let be an -path with both endpoints on the inner layer. Let be a cyclic neighbor of that does not share an edge with , and assume by symmetry.
In the first three cases we try to create a new level edge between and .
Case 1: If does not see , then ObstrReduction reduces the potential in according to Lemma 8.
Case 2: If sees and the incoming edge of is a non level edge, then flipping it to instantly decreases the potential.
Case 3: If sees and is the end, then we can pick any non level edge and flip it to to decrease the potential.
So now, suppose that sees , and the incoming edge of is a level edge. Cases 4-6 follow different strategies depending on the type of .
Case 4: If is a small diagonal, the idea is that we can rotate that diagonal, with as an anchor, via the flips followed by . 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:
are neighbors and see each other;
is a small diagonal with ,

Figure 8. Rotation of a small diagonal in flips until the potential decreases.
and the termination is implied by the fact that after an iteration of the loop, the couple is shifted clockwise, so if the loop does not stop earlier, the diagonal will rotate until it becomes a level edge, when becomes . This loop can rotate that diagonal at most times, meaning that the reduction step in this case takes flips.
– Case 5: If is a medium diagonal, the idea is to use first rotate the diagonal until the potential diminishes as illustrated in Figure 9, or does not see (Case 5.(a)), and then if the potential has not already be diminished, use the procedure DiagObstrReduction on the obstruction between and (Case 5.(b)).

Figure 9. Rotation of a medium diagonal in Case 5.(a) of InnerReduction in flips.
The proof for the validity of Case 5.(a) is similar to Case 4, so let’s focus on Case 5.(b). If does not see , and is on the other side of the medium diagonal, we can show that the path verifies the premises of Lemma 9. Let and . Then since does not see , the path must enter the triangle without crossing (planarity) or (assumption). Thus the existance of an inner point the closest to . Then we can prove that sees and .
Also, we can observe that the prefix must contain an outer point. Let be the last one of that prefix. Then the idea is that 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 sees , we can deduce that the path cannot visit any outer point before reaching without crossings. And similar planarity restrictions enforce the prefix to visit a subset of points of in clockwise order, and the subpath to contain at least all the points of between and in counterclockwise order. Therefore the premises of DiagObstrReduction are met and it can reduce the potential in flips. An example of a path in this case is given in Figure 10.

Figure 10. Prefix structure of the path in Case 5.(b) of InnerReduction
Case 6: If 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 To enforce stong properties on the path, suppose and are in clockwise order (otherwise we can come back to this case with a single flip). Then let be the first outer point visited by the path. Then we can show that the polygonal line formed by and splits the points in half, with the suffix on the left side, and the subpath on the left as illustrated in Figure 11. We can deduce from this structure that the prefix must visit every outer point from to in clockwise order. So the last outer point visited before was . Let . If sees (Case 6.(a).i), then the flip transforms a bridge or medium diagonal into a small diagonal, and creates a level edge on the as illustrated in Figure 12

Figure 11. Illustration of the dashed polygonal line separating the points in two parts in Case 6.(a) 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 blocking the vision between and . Let be the last small diagonal of that subpath. Then only contains level edges and sees so the flip 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 . That point does not share an edge with because otherwise would have had to cross . Therefore when applying this procedure, the choice of for the neighbor of the start of the new path is valid, and we can show that in , if the incoming edge of is a level edge, its outgoing edge is a bridge and it sees , then that bridge must be crossing the subpath . Therefore Case 6 cannot be applied again in , so one of the other ones will. So in the worst case, the potential will be diminished in flips. An illustration of that case is presented in Figure 13.

Figure 13. Reduction from Case 6.(a).ii to other cases of InnerReduction.
Case 6.(b) Otherwise . 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 be the first small diagonal of . It must exist as is not in . Then has neighbor not seen by , and cannot be connected to because otherwise would need to cross . So after the flip , becomes the start of the new path and is a valid choice for the neighbor of in the recursive call of the procedure for . Also, we can be sure that will not fall again into Case 6.(b) since , so and therefore . So in the worst case, the potential will be diminished in 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 flips to reduce the potential.
Obstruction procedures and proof of Lemmas 8 and 9
Procedure ObstrReduction.
Input: a path whose start does not see one of its neighbor . Assume by symmetry. Let be the closest edge to intersecting , with .
If sees , perform .
Else follow the procedure DiagObstrReduction.
Procedure DiagObstrReduction. Input: A path starting at such that there is a medium or big diagonal , with , intersecting the convex hull of the inner layer next to and another vertex . Suppose also that is inside the triangle , and that the prefix visits a subset of in circular order from to , and the subpath visits all the points between and skipped by the prefix (without particular order), and all the outer points in order from (the first neighbor of visited by after ) to (the last outer point visited before ).
Suppose without loss of generality that the crossing of the diagonal is counterclockwise to . Let , and .
If , perform
Else if , perform
Else if does not see :
Let , with , be the closest edge intersecting and perform
Otherwise, perform
(a) If , let and perform
(b) Else if ,
Let and and perform
(c) Otherwise, and .
i. if does not see , recursively apply DiagObstrReduction on the obstruction between and .
ii. Else if the incoming edge of is not level, perform
iii. Otherwise, perform
Proof (Lemma 8). Let be an -path whose start does not see one of its neighbor , and assume by symmetry. Let be the closest edge to intersecting . Then 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 , sees either or .
Case 1. If sees , then the flip is legal and we can show by case exhaustion that no matter the type of initially, that flip decreases the potential. The different subcases are illustrated in Figure 15.

Figure 15. (a) is an inner point; (b) is an outer point next to ; (c) is an outer point far from . Immediate potential reduction in case 1 of ObstrReduction
Case 2. Otherwise, does not see but sees , so we can deduce that the diagonal must be a big diagonal, otherwise, would have been able to see . We can now show that the path has the strong structural properties that enable the use of the procedure DiagObstrReduction.
Since does not see , the path must enter the triangle without crossing (planarity) or (assumption). so that triangle contains at least 1 point of inside of it. Let be the closest point to inside that triangle. Then we can prove that there is no other point inside the concave quadrilateral or that would contradict the definition of , therefore sees both and .
Now, since is a big diagonal, it splits the point set in two parts, and in particular, it must separate the start from the end because otherwise an entire side could not be visited without crossings. This means that the prefix must visit the entire left side of . Moreover, since the quadrilateral cannot be crossed by the path, we can deduce that the prefix cannot visit any point of without introducing crossings or violating the definition of or . Therefore must visit at least all the outer points from to . With the same argument, we can observe that must visit that subset of in clockwise order and all the outer points of the left side are visited in counterclockwise order in . The structure of the prefix of that path is illustrated in Figure 16.

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 flips.
Therefore in both cases, the potential of the path can be reduced in flips.
Proof (Lemma 9). The main goal of this procedure is to remove the diagonal by flipping it to , or to remove any other heavy weight edge encountered in the prefix. This procedure does it by successively eliminating simple cases.
Let . A first easy case is when the successor of is an inner point.
– Case 1. If , we can make the new starting point with 2 flips: followed by . These flips are legal since sees and is an empty triangle of where two of the borders cannot be crossed by planarity, so sees . After these two flips, the potential may have increased by 1 at most. However, the last flip 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

Figure 17. Reduction of potential in Case 1 of DiagObstrReduce
Suppose now that . Since by assumption the subpath visits all the outer points from to in counterclockwise order, we can deduce that . Let . The case analysis is now refined based on the position of in the path
– Case 2. If , then since by assumption on , that prefix visit points of 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 and see each other. Indeed, if that was not the case, the convexity of would prevent the quadrilateral from being concave, which would mean that would see , 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 flips.

Figure 18. Reduction of potential in Case 2 of DiagObstrReduction
Case 3. If and does not see , then there is a medium diagonal blocking the view between those points. Let be the closest edge to intersecting . Then we can show that necessarily and , otherwise there would need to be some crossings in the path. We can also show that sees since the triangle is empty and the path cannot cross (planarity) nor can it cross (definition of ). So after the first neutral flip , the flip reduced the potential by at least 2 as illustrated in Figure 19.

Figure 19. Reduction of potential in Case 3 of DiagObstrReduction.
Now suppose sees and (Case 4.), i.e. . Then like all the previous cases, we start flipping to form a new path as illustrated in Figure 20. In this case, we know that is not a cyclic neighbor of in the path, so is a small diagonal, just like . Therefore .

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 . We can observe that 2 cases can be solved easily.
Case 4.(a): If , 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.

Figure 21. Reduction of potential in Case 4.(a) of DiagObstrReduction.
Case 4.(b) If and , then by the assumption on the path, we know that is the clockwise neighbor of . In this case we can just connect them in 2 flips. By the same empty triangle argument we know that sees , and since they are outer layer neighbor, we know that sees , 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.

Figure 22. Reduction of potential in Case 4.(b) of DiagObstrReduction.
Now suppose and . In this case, the outgoing edge of 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 to flipping . However, the edge is in the wrong direction to be flipped directly. Therefore we use 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 does not see , 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 sees and is not a level edge, then the flip creates a level edge, reducing the potential.
Case 4.(c).iii if sees and is a level edge, then the flip makes the new start, and reverses the order of the path in as displayed in Figure 23.

Figure 23. Reduction of potential in Case 4.(c).iii of DiagObstrReduction.
The second flip is valid since after the first flip, sees which is connected to which sees , and all these points form an empty quadrilateral, so sees .
Now to prove that the potential reduces, we must prove that in , the outgoing edge of is a medium diagonal, and that after the first flip, the order of the path in is reversed, meaning that that medium diagonal is flipped for a small one in the second flip.
Since and , the outgoing edge of is either a bridge or a medium diagonal. Suppose for contradiction that it is a bridge, and consider the simple loop where lies outside except at its endpoints and . By the Jordan curve theorem, separates the plane into two regions. Since is a bridge and is a neighbor of , the region containing contains no point of other than and at its border, so in particular, it does not contain . Therefore must cross , but it cannot cross and (assumption), it cannot cross (planarity) and it cannot cross (outside the hull). This contradiction shows that is a medium diagonal.
We can also show with a different loop that must be visited before in , therefore after the first flip, the medium diagonal of 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 flips.
Proof of Lemma 5
Using Lemma 4 alone, we would get a flip complexity of in the worst case. In this section we prove that the expensive cases where we may need flips in a reduction step does not happen too often. In fact, we show that at most reduction steps may need strictly more than 1 flip to be performed.
First, we can observe that the number of bridges , the number of small diagonals , and the number of medium diagonals are all bounded by as these edge types all have an extremity in . Therefore, we just need to show that most of the big diagonals can be removed in 1 flip throughout the reduction process.
Let be the set of boundary segments of induced by the vertices of .
Let be a path. For , let denote the set of big diagonals whose two intersections with belong respectively to the intervals and . We also denote by the set of big diagonals that do not intersect , so that forms a partition of the set of big diagonals of . Because of the planarity of the path, the support of that partition is (Lemma 10).
Lemma 10. For any given path , the number of non-empty sets is .
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 .
The graph whose vertices are the segments of (i.e. ) and whose edges correspond to non-empty sets is therefore outerplanar. Since , it contains only edges. Hence only sets are non-empty.
This partition of the big diagonals enables the following observation.
Observation 11. Let be a path. As soon as one big diagonal of has been flipped, we can transform every remaining diagonal of to level edges using one flip per diagonal.
Proof. Suppose , for , and suppose we are about to flip one diagonal of . 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 be the first and be last diagonal of .
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 and , we can deduce that there is no endpoint in the region of the plane between the lines and . So no other diagonal from can be visible by the endpoints, therefore, by symmetry we can suppose that is the diagonal we are about to flip, and that will become the next starting point.
By definition of , there is no inner point in the region between the lines and , so the vertices of the subpath are in convex position. This forces a particular structure where each successive diagonal are connected by level edges, and as soon as has been flipped, so that 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 . ⊓⊔
Therefore, according to Observation 11, at most 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 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]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]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]Akl, S.G., Islam, M.K., Meijer, H.: On planar path transformation. Inf. Process. Lett. 104, 59–64 (2007)
- [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]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]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]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

