Home

Browse
Communities
& Collections

Issue Date
Author
Title
Subject

Sign on to:

My Account
authorized users

Edit Profile

Help
 Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/9470

 Title: On the mixing rate of the triangulation walk Authors: Molloy, M.Reed, B.Steiger, W. Keywords: computational geometrygraph theoryrandomised algorithmsmixing ratetriangulation walkconvex polygonrandom walkinternal diagonals Issue Date: Sep-1998 Publisher: American Mathematical Society Citation: Molloy, M., Reed, B., & Steiger, W. (1998). On the mixing rate of the triangulation walk. Pardalos, P., Rajasekaran, S., Rolim, J. (Eds.). Proceedings of DIMACS Workshop on Randomization Methods in Algorithm Design, 12-14 Dec. 1997, Princeton, NJ, USA (Vol. 43, pp. 179-190). USA: American Mathematical Society 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-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β). A direct argument is given for the fact that the mixing rate is at least Ω(n3/2) Description: Material in this book may be reproduced by any means for educational and scientific purposes without fee or permission with the exception of reproduction by services that collect fees for delivery of documents and provided that the customary acknowledgment of the source is given. This consent does not extend to other kinds of copying for general distribution, for advertising or promotional purposes, or for resale. Requests for permission for commercial use of material should be addressed to the Acquisitions Department, American Mathematical Society, 201 Charles Street, Providence, RI 02904-2294 USA. Requests can also be made by email to reprint-permission@ams.org . Excluded from these provisions is material in articles for which the author holds copyright. In such cases, requests for permission to use or reprint should be addressed directly to the author(s). Copyright ownership is indicated in the notice in the lower right-hand corner of the first page of each article. URI: http://hdl.handle.net/1807/9470 ISBN: 0821809164 Appears in Collections: Mathematics

Files in This Item:

File Description SizeFormat
on the mixing rate of the triangulation walk.pdf259.57 kBAdobe PDF
View/Open