2001
Every set of disjoint line segments admits a binary tree
Publication
Publication
Discrete and Computational Geometry , Volume 26  Issue 3 p. 387 410
Given a set of n disjoint line segments in the plane, we show that it is always possible to form a tree with the endpoints of the segments such that each line segment is an edge of the tree, the tree has no crossing edges, and the maximum vertex degree of the tree is 3. Furthermore, there exist configurations of line segments where any such tree requires degree 3. We provide an O (n log n) time algorithm for constructing such a tree, and show that this is optimal.
Additional Metadata  

doi.org/10.1007/s004540010042y  
Discrete and Computational Geometry  
Organisation  School of Computer Science 
Bose, P, Houle, M.E. (M. E.), & Toussaint, G.T. (G. T.). (2001). Every set of disjoint line segments admits a binary tree. Discrete and Computational Geometry, 26(3), 387–410. doi:10.1007/s004540010042y
