Pointed and colored binary encompassing trees

摘要

For n disjoint line segments in the plane we construct in optimal O(n log n) time an encompassing tree of maximum degree three such that at every vertex all incident edges lie in a halfplane defined by the incident input segment. In particular, this implies that each vertex is pointed. Furthermore, we show that any set of colored disjoint line segments (for each segment one endpoint is colored red and the other endpoint is colored blue) has an encompassing tree of maximum degree three in which no edge is monochromatic.