Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 11, 2010, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Michael Hoffmann
For n disjoint line segments in the plane we construct in optimal O (n log n) time and linear space an encompassing tree of maximum degree three such that at every vertex v all edges of the tree that are incident to v lie in a halfplane bounded by the line through the input segment which v is an endpoint of. In particular, this tree is pointed since every vertex has an incident angle greater than π. Such a pointed binary tree can be augmented to a minimum pseudo-triangulation. It follows that every set of disjoint line segments in the plane has a constrained minimum pseudo-triangulation whose maximum vertex degree is bounded by a constant.
Automatic MiSe System Software Version 1.4803M | admin login