@inproceedings{fca4c0e473fa45bab1eb3864ff603842,

title = "Every set of disjoint line segments admits a binary tree",

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 at least degree 3. We provide an O(n log n) time algorithm for constructing such a tree, and show that this is optimal.",

author = "Prosenjit Bose and Houle, {Michael E.} and Godfried Toussaint",

note = "Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 5th Annual International Symposium on Algorithms and Computation, ISAAC 1994 ; Conference date: 25-08-1994 Through 27-08-1994",

year = "1994",

doi = "10.1007/3-540-58325-4_162",

language = "English (US)",

isbn = "9783540583257",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "20--28",

editor = "Ding-Zhu Du and Ding-Zhu Du and {Zhang }, Xiang-Sun",

booktitle = "Algorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings",

}