@inproceedings{ba20073bd37d40b79a9cd645672ead42,
title = "The zigzag path of a pseudo-triangulation",
abstract = "We define the zigzag path of a pseudo-triangulation, a concept generalizing the path of a triangulation of a point set. The pseudo-triangulation 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 pseudo-triangulation 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 pseudo-triangulations of a point set.",
author = "O. Aichholzer and G. Rote and B. Speckmann and I. Streinu",
year = "2003",
doi = "10.1007/978-3-540-45078-8_33",
language = "English",
isbn = "3-540-40545-3",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "377--388",
editor = "F.K.H.A. Dehne and J.R. Sack and M.H.M. Smid",
booktitle = "Algorithms and Data Structures (Proceedings 8th International Workshop, WADS 2003, Ottawa, Ontario, Canada, July 30-August 1, 2003)",
}