Every set of disjoint line segments admits a binary tree

Authors
Bose, P Houle, ME Toussaint, GT
Citation
P. Bose et al., Every set of disjoint line segments admits a binary tree, DISC COM G, 26(3), 2001, pp. 387-410
Citations number
17
Categorie Soggetti
Engineering Mathematics
Journal title
DISCRETE & COMPUTATIONAL GEOMETRY
ISSN journal
01795376 → ACNP
Volume
26
Issue
3
Year of publication
2001
Pages
387 - 410
Database
ISI
SICI code
0179-5376(200110)26:3<387:ESODLS>2.0.ZU;2-W
Abstract
Given a set of n disjoint line segments in the plane, we show that it is al ways possible to forma tree with the endpoints of the segments such that ea ch 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 confi gurations of line segments where any such tree requires degree 3. We provid e an O(n log n) time algorithm for constructing such a tree, and show that this is optimal.