The Fermat star of binary trees

摘要

A Fermat point P is one that minimizes the sum δ of the distances between P and the points of a given set. The resulting arrangement, called here a Fermat star, is a particular Steiner tree with only one intermediate point. We extend these concepts to rooted binary trees under the known rotation distance that measures the difference in shape of such trees. Minimizing δ is hard, due to the intrinsic difficulty of computing the rotation distance. Then we limit our study to establishing significant upper bounds for S. In particular, for m binary trees of n vertices, we show how to construct efficiently a Fermat star with δ ≤ mn - 3m, with a technique inherited from the studies on rotation distance.