Abstract
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(nlog n) time algorithm for constructing such a tree, and show that this is optimal.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received September 14, 1999, and in revised form January 17, 2001. Online publication August 29, 2001.
Rights and permissions
About this article
Cite this article
Bose, P., Houle, M. & Toussaint, G. Every Set of Disjoint Line Segments Admits a Binary Tree. Discrete Comput Geom 26, 387–410 (2001). https://doi.org/10.1007/s00454-001-0042-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-001-0042-y