论文标题
重新配置非跨树木
Reconfiguration of Non-crossing Spanning Trees
论文作者
论文摘要
对于$ n $ n $点的一组$ p $在一般位置的$ n $点，一棵非交叉跨越树是一个点的生成树，其中每个边缘都是一对点之间的直线段，而没有两个边缘相交，除了共同的端点。我们研究了使用一系列翻转序列重新配置$ p $的一棵非交叉的跨越树的问题，每个翻转序列都可以消除一个边缘并添加一个新的边缘，以便结果再次是$ p $的非交叉跨越树。有一个已知的上限为$ 2n-4 $翻转[Avis and Fukuda，1996]，下限为$ 1.5N-5 $翻转。我们提供了一种重新配置算法，该算法最多使用$ 2N-3 $翻转，但在一棵树是一条路径时，将其降低到$ 1.5N-2 $翻转：这些点位于凸位；或该路径在某个方向上是单调的。对于凸位的点，我们证明了$ 2D-Ω（\ log d）$的上限，其中$ d $是树木之间对称差的一半。我们还检查了快乐边缘是否需要翻转的快乐边缘（最初和最后一棵树的共有树），并使用详尽的搜索找到了小点集的确切最小翻转距离。
For a set $P$ of $n$ points in the plane in general position, a non-crossing spanning tree is a spanning tree of the points where every edge is a straight-line segment between a pair of points and no two edges intersect except at a common endpoint. We study the problem of reconfiguring one non-crossing spanning tree of $P$ to another using a sequence of flips where each flip removes one edge and adds one new edge so that the result is again a non-crossing spanning tree of $P$. There is a known upper bound of $2n-4$ flips [Avis and Fukuda, 1996] and a lower bound of $1.5n - 5$ flips. We give a reconfiguration algorithm that uses at most $2n-3$ flips but reduces that to $1.5n-2$ flips when one tree is a path and either: the points are in convex position; or the path is monotone in some direction. For points in convex position, we prove an upper bound of $2d - Ω(\log d)$ where $d$ is half the size of the symmetric difference between the trees. We also examine whether the happy edges (those common to the initial and final trees) need to flip, and we find exact minimum flip distances for small point sets using exhaustive search.
