Rotation distance between rooted binary trees measures the degree of similarity of two trees with ordered leaves and is equivalent to edge-flip distance between triangular subdivisions of regular polygons. There are no known polynomial-time algorithms for computing rotation distance. Existence of common edges makes computing rotation distance more manageable by breaking the problem into smaller subproblems. Here we describe the distribution of common edges between randomly-selected triangulations and measure the sizes of the remaining pieces into which the common edges separate the polygons. We find that asymptotically there is a large component remaining after sectioning off numerous small polygons which gives some insight into the distribution of such distances and the difficulty of such distance computations, and we analyze the distributions of the sizes of the largest and smaller resulting polygons.
@article{10_37236_2541,
author = {Sean Cleary and Andrew Rechnitzer and Thomas Wong},
title = {Common edges in rooted trees and polygonal triangulations},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {1},
doi = {10.37236/2541},
zbl = {1267.05249},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2541/}
}
TY - JOUR
AU - Sean Cleary
AU - Andrew Rechnitzer
AU - Thomas Wong
TI - Common edges in rooted trees and polygonal triangulations
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/2541/
DO - 10.37236/2541
ID - 10_37236_2541
ER -
%0 Journal Article
%A Sean Cleary
%A Andrew Rechnitzer
%A Thomas Wong
%T Common edges in rooted trees and polygonal triangulations
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2541/
%R 10.37236/2541
%F 10_37236_2541
Sean Cleary; Andrew Rechnitzer; Thomas Wong. Common edges in rooted trees and polygonal triangulations. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/2541
