Vol. 8, No. 5, 2015

Download this article
Download this article For screen
For printing
Recent Issues

Volume 17
Issue 3, 363–541
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Editors' interests
 
Subscriptions
 
ISSN (electronic): 1944-4184
ISSN (print): 1944-4176
 
Author index
To appear
 
Other MSP journals
Expected maximum vertex valence in pairs of polygonal triangulations

Timothy Chu and Sean Cleary

Vol. 8 (2015), No. 5, 763–770
Abstract

Edge-flip distance between triangulations of polygons is equivalent to rotation distance between rooted binary trees. Both distances measure the extent of similarity of configurations. There are no known polynomial-time algorithms for computing edge-flip distance. The best known exact universal upper bounds on rotation distance arise from measuring the maximum total valence of a vertex in the corresponding triangulation pair obtained by a duality construction. Here we describe some properties of the distribution of maximum vertex valences of pairs of triangulations related to such upper bounds.

Keywords
random binary trees
Mathematical Subject Classification 2010
Primary: 05C05, 68P05
Milestones
Received: 6 March 2014
Revised: 17 October 2014
Accepted: 22 November 2014
Published: 28 September 2015

Communicated by Kenneth S. Berenhaut
Authors
Timothy Chu
Department of Computer Science
The City College of New York
City University of New York
New York, NY 10031
United States
Sean Cleary
Department of Mathematics
The City College of New York and the CUNY Graduate Center
City University of New York
NAC R8133
160 Convent Avenue
New York, NY 10031
United States