| On the mixing rate of the triangulation walk (1999) | |||||||||||||||
Abstract | |||||||||||||||
| Let T n denote the set of triangulations of a convex polygon K with n sides. We study the random walk on T n whose transitions are \ ips" of one of the n 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 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||