| On the Mixing Rate of the Triangulation Walk (Abstract) (2007) | |||||||||||||
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 fi A direct argument is given for the fact that the mixing rate is at least\Omega\Gamma n | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||