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 -