## 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(n^{2}) time per path and O(n^{2})
space.
Last update: May 28, 2003.