论文标题
改进了凸多边形三角剖分式散步的混合
Improved mixing for the convex polygon triangulation flip walk
论文作者
论文摘要
We prove that the well-studied triangulation flip walk on a convex point set mixes in time O(n^3 log^3 n), the first progress since McShine and Tetali's O(n^5 log n) bound in 1997. In the process we give lower and upper bounds of respectively Omega(1/(sqrt n log n)) and O(1/sqrt n) -- asymptotically tight up to an O(log n）因子 - 为了扩展AssociaHedron Graph K_n。上限恢复了Molloy，Reed和Steiger的Omega（N^{3/2}），绑定在步行的混合时间上。为了获得这些结果，我们引入了一个框架，该框架由一组足够的条件组成，其中给定的马尔可夫链会迅速混合。该框架是一个纯粹的组合类似物，在某些情况下，它比Jerrum，Son，Tetali和Vigoda的投影限制技术更好。特别是，除了对三角剖分的结果外，我们还显示了固定k> = 4在凸点集合的k型旋转翻转步行中的准化合物混合。
We prove that the well-studied triangulation flip walk on a convex point set mixes in time O(n^3 log^3 n), the first progress since McShine and Tetali's O(n^5 log n) bound in 1997. In the process we give lower and upper bounds of respectively Omega(1/(sqrt n log n)) and O(1/sqrt n) -- asymptotically tight up to an O(log n) factor -- for the expansion of the associahedron graph K_n. The upper bound recovers Molloy, Reed, and Steiger's Omega(n^{3/2}) bound on the mixing time of the walk. To obtain these results, we introduce a framework consisting of a set of sufficient conditions under which a given Markov chain mixes rapidly. This framework is a purely combinatorial analogue that in some circumstances gives better results than the projection-restriction technique of Jerrum, Son, Tetali, and Vigoda. In particular, in addition to the result for triangulations, we show quasipolynomial mixing for the k-angulation flip walk on a convex point set, for fixed k >= 4.
