test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works

Advanced Search
& Collections
Issue Date   
Sign on to:   
Receive email
My Account
authorized users
Edit Profile   
About T-Space   

T-Space at The University of Toronto Libraries >
University of Toronto at Scarborough >
Computer and Mathematical Science >
Mathematics >

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 geometry
graph theory
randomised algorithms
mixing rate
triangulation walk
convex polygon
random walk
internal 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

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.