|
|||||
 |
|
|
|
|
|
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 |
|
|
