Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, January 27, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Bettina Speckmann (TU Eindhoven)
We define the zigzag path of a pseudo-triangulation, a concept generalizing the path of a triangulation of a point set. The pseudotriangulation zigzag path allows us to use divide-and-conquer type of approaches for suitable (i.e., decomposable) problems on pseudo-triangulations. For this we provide an algorithm that enumerates all pseudotriangulation zigzag paths (of all pseudo-triangulations of a given point set with respect to a given line) in O(n^2) time per path and O(n^2) space, where n is the number of points. We illustrate applications of our scheme which include a novel algorithm to count the number of pseudotriangulations of a point set.
Automatic MiSe System Software Version 1.4803M | admin login