
Sean Cleary

Andrew Rechnitzer

Thomas Wong
Keywords:
Enumeration, triangulations, rotation distance
Abstract
Rotation distance between rooted binary trees measures the degree of similarity of two trees with ordered leaves and is equivalent to edgeflip distance between triangular subdivisions of regular polygons. There are no known polynomialtime 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 randomlyselected 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.