Diagonal Flips in Hamiltonian Triangulations on the Sphere
Diagonal Flips in Hamiltonian Triangulations on the Sphere
复制标题
DOI：
10.1007/s00373-002-0508-6
复制
发表时间：
2003-11
影响因子：
0.7
通讯作者：
Ryuichi Mori;Atsuhiro Nakamoto;K. Ota
中科院分区：
文献类型：
--
作者：
Ryuichi Mori;Atsuhiro Nakamoto;K. Ota
本文证明了球面上n ≥5个顶点的任意两个Hamilton三角剖分最多可以通过4 n −20次对角翻转相互转化，并保持汉密尔顿圈的存在性.此外，利用这个结果，我们将证明，对于n顶点球面上的任意两个三角剖分，最多需要6 n-30次对角翻转才能相互转换。
In this paper, we shall prove that any two Hamiltonian triangulations on the sphere withn≥5 vertices can be transformed into each other by at most 4n−20 diagonal flips, preserving the existence of Hamilton cycles. Moreover, using this result, we shall prove that at most 6n−30 diagonal flips are needed for any two triangulations on the sphere withnvertices to transform into each other.