Vol. 8, No. 5, 2015

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

Volume 11, 1 issue

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
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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