| On the mixing rate of the triangulation walk (1999) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract Let Tn denote the set of triangulations of a convex polygon K with n sides. We study the random walk on Tn whose transitions are "flips " of one of the n \Gamma 3 internal diagonals of the current triangulation, the choice of diagonal being random. By bounding the conductance of this graph we show that the walk mixes rapidly, namely in time O(n 8). A direct argument is given for the fact that the mixing rate is at least \Omega (n 3=2 1 Introduction and Summary Consider a convex polygon K on n points p1; : : : ; pn, in clockwise order. A triangulation is a set of n \Gamma 3 non-crossing diagonals pipj which partitions K into n \Gamma 2 triangles. It is familiar that Tn, the set of all triangulations of K, satisfies | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||