| Every set of disjoint line segments admits a binary tree, Discrete Comput Geom (2008) | |||||||||||||||
Abstract | |||||||||||||||
| z 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(n log n) time algorithm for constructing such a tree, and show that this is optimal. 1 Introduction Given a set of disjoint line segments, determining whether the set admits certain combinatorial structures has received considerable attention. One of the best-studied such structures has been the simple circuit or polygon through a set of line segments. The question of deciding whether a set of disjoint line segments admits a simple circuit is conjectured to be NP-complete, since Rappaport [12] has shown that deciding whether a set of line segments allowed to intersect at their endpoints admits a simple circuit is an NP-complete problem. For certain special cases, however, polynomialtime algorithms have been obtained. Avis and Rappaport [1] gave an O(n | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||