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


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.

  PostScript file (gzipped)
other papers about this subject
Last update: May 28, 2003.