← 研踪 PaperTrailarXiv:2611.03299 · v1
Quadratic Reconfiguration of Plane Spanning Paths on Two-Layer Point Sets
首次提交 2026-11-02 23:34
版本更新 2026-11-02 23:34
雷达观测 2026-11-04 23:41
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-02 23:34 · 最新观测版本
Quadratic Reconfiguration of Plane Spanning Paths on Two-Layer Point Sets
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.
查看此版本解读 →查看此版本原文 ↗