Quadratic flips transform plane spanning paths on two-layer points
Quadratic Reconfiguration of Plane Spanning Paths on Two-Layer Point Sets
Computational Geometry
Summary
The paper studies how to change one non-crossing path that connects points in the plane into another such path by swapping edges, without creating any crossings. Earlier work showed this is always possible for points arranged in two layers but might require many swaps. The authors improve this by proving that the number of swaps needed grows only quadratically with the number of points, making the process more efficient. This advance helps understand how complex geometric structures can be systematically modified step-by-step.
What this means in practice
- •For computational geometers: Optimize algorithms that reconfigure planar graph structures efficiently within quadratic time on two-layer point sets.
- •For network designers: Design and update planar network routes without crossings using guaranteed quadratic steps on layered layouts.
A theory result. No direct application yet.
Authors
Samuel Avril, Yan Gerard, Guilherme D. da Fonseca
Abstract
Consider a crossing-free polygonal path with $n$ 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(n^2)$ flips suffice. More precisely, for a two-layer point set $S=L_0\cup L_1$, where $L_0$ and $L_1$ denote the outer and inner layers, respectively, our method uses $O(|L_0|+|L_1|^2)$ flips.