We show that for any set of disjoint line segments in the plane there exists a pointed binary encompassing tree T, that is, a spanning tree on the segment endpoints that contains all input segments, has maximum degree three, and every vertex v $\in$ T is pointed, that is, v has an incident angle greater than $\pi$. Such a tree can be completed to a minimum pseudo-triangulation. In particular, it follows that every set of disjoint line segments has a minimum pseudo-triangulation of bounded vertex degree.
|Title of host publication||Algorithm Theory - SWAT 2004 (Proceedings 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004)|
|Editors||T. Hagerup, J. Katajainen|
|Place of Publication||Berlin|
|Publication status||Published - 2004|
|Name||Lecture Notes in Computer Science|