Every set of disjoint line segments admits a binary tree

P. Bose, M. E. Houle, G. T. Toussaint

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)387-410
Number of pages24
JournalDiscrete and Computational Geometry
Issue number3
StatePublished - Oct 2001

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Every set of disjoint line segments admits a binary tree'. Together they form a unique fingerprint.

Cite this