TY - GEN
T1 - Pointed binary encompassing trees
AU - Hoffmann, M.
AU - Speckmann, B.
AU - Tóth, Cs.D.
PY - 2004
Y1 - 2004
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-540-27810-8_38
DO - 10.1007/978-3-540-27810-8_38
M3 - Conference contribution
SN - 3-540-22339-8
T3 - Lecture Notes in Computer Science
SP - 442
EP - 454
BT - Algorithm Theory - SWAT 2004 (Proceedings 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004)
A2 - Hagerup, T.
A2 - Katajainen, J.
PB - Springer
CY - Berlin
ER -