Oswin Aichholzer, Günter Rote, Bettina Speckmann, and Ileana
Streinu:
The zigzag path of a pseudo-triangulation
In: "Algorithms and Data Structures". Proceedings of the 8th
International Workshop on Algorithms and Data Structures (WADS 2003),
Ottawa, July 2003. Editors: Frank Dehne, Jörg-Rüdiger
Sack, and Michiel Smid. Lecture Notes in Computer Science 2748,
Springer-Verlag, 2003, pp. 377–388. doi:10.1007/978-3-540-45078-8_33
Abstract
The concept of a zigzag path of a pseudotriangulation is a tool that
allows to solve counting and optimization problems for
pseudottriangulations in a divide-and-conquer style. We present an
algorithm that enumerates all zigzag paths of a given point set with
respect to a given line in O(n2) time per path and O(n2)
space.
Last update: May 28, 2003.