Growing a Tree from Its Branches

✍ Scribed by P. Bose; G. Toussaint

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 714 KB
• Volume: 19
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1995.1028

✦ Synopsis

Given a set (l) of (n) disjoint line segments in the plane, we show that it is always possible to form a spanning tree of the endpoints of the segments, such that each line segment is an edge of the tree and the tree 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 computed in (O\left(n^{2}\right)) time, and second that the maximum degree of a node in the minimum weight spanning tree formed by these line segments is seven, and that there exists a set of line segments achieving this bound. Finally, we show that the complexity of finding the minimum weight spanning tree is optimal ((\boldsymbol{m})(n \log n)) when we assume that the endpoints of the line segments are in general position.

ce: 1945 Acidemic Press, Inc