GROWING A TREE FROM ITS BRANCHES

Given a set L of n disjoint line segments in the plane, we show that i t is always possible to form a spanning tree of the endpoints of the s egments, such that each line segment is an edge of the tree and the tr ee has no crossing edges. Such a tree is known as an encompassing tree and can be constructed in O(n log n) time when no three endpoints in L are collinear. In the presence of collinear endpoints, we show first that an encompassing tree with no crossing edges exists and can be co mputed in O(n(2)) time, and second that the maximum degree of a node i n the minimum weight spanning tree formed by these line segments is se ven, and that there exists a set of line segments achieving this bound . Finally, we show that the complexity of finding the minimum weight s panning tree is optimal O(n log n) when we assume that the endpoints o f the line segments are in general position. (C) 1995 Academic Press, Inc.