论文标题
在平面之间的点之间禁止边缘，以断开三角剖分翻盖图
Forbidding Edges between Points in the Plane to Disconnect the Triangulation Flip Graph
论文作者
论文摘要
飞机上的一组$ p $点的翻转图都有一个$ p $的三角剖分的顶点，当两个三角剖分差异一个翻转时，一个边缘是一个边缘，将一个三角剖分边缘替换为另一个三角形边缘。已知翻转图具有一些连接性属性：（1）翻转图已连接； （2）连通性仍然存在于三角形时，该连通性在两个点之间包含一些受约束的边缘； （3）对于$ p $在尺寸$ n $的一般位置，翻转图是$ \ lceil \ frac {n} {2} {2} -2 \ rceil $ - 连接，这是Wagner和welzl（Soda 2020）的最新结果。 当禁止点之间的某些边缘时，我们介绍了翻转图的连接性能的研究。如果消除包含$ e $的三角形，则在两个点之间的边缘$ e $是在断开的翻转图中结果。更一般而言，如果消除所有包含$ x $的边缘的三角形，则在$ p $ $ p $的点之间的$ x $边缘是一个翻转剪裁集。 $ p $的翻转切割数是翻转切割套件的最小尺寸。 我们给出了翻转剪切边缘的特征，该边缘导致$ O（n \ log n）$ time算法来测试边缘是否是翻转剪切边缘，并且随着预处理的预处理，$ o（n）$ time算法可以测试两个三角形是否在flip graph的相同连接组件中是否相同。对于凸出位置的一组$ n $点（其翻转图是AssociaHedron的1型骨骼），我们证明了Flip Cut Number为$ n-3 $。
The flip graph for a set $P$ of points in the plane has a vertex for every triangulation of $P$, and an edge when two triangulations differ by one flip that replaces one triangulation edge by another. The flip graph is known to have some connectivity properties: (1) the flip graph is connected; (2) connectivity still holds when restricted to triangulations containing some constrained edges between the points; (3) for $P$ in general position of size $n$, the flip graph is $\lceil \frac{n}{2} -2 \rceil$-connected, a recent result of Wagner and Welzl (SODA 2020). We introduce the study of connectivity properties of the flip graph when some edges between points are forbidden. An edge $e$ between two points is a flip cut edge if eliminating triangulations containing $e$ results in a disconnected flip graph. More generally, a set $X$ of edges between points of $P$ is a flip cut set if eliminating all triangulations that contain edges of $X$ results in a disconnected flip graph. The flip cut number of $P$ is the minimum size of a flip cut set. We give a characterization of flip cut edges that leads to an $O(n \log n)$ time algorithm to test if an edge is a flip cut edge and, with that as preprocessing, an $O(n)$ time algorithm to test if two triangulations are in the same connected component of the flip graph. For a set of $n$ points in convex position (whose flip graph is the 1-skeleton of the associahedron) we prove that the flip cut number is $n-3$.
