Pseudo-Triangulations from Surfaces and a Novel Type of Edge Flip

O. Aichholzer, F. Aurenhammer, P. Brass, and H. Krasser

Abstract:

We prove that planar pseudo-triangulations have realizations as polyhedral surfaces in three-space. Two main implications are presented: The spatial embedding leads to a novel flip operation that allows for a drastical reduction of flip distances, especially between (full) triangulations. Moreover, several key results for triangulations, like flipping to optimality, (constrained) Delaunayhood, and a convex polytope representation, are extended to pseudo-triangulations in a natural way.

Reference: O. Aichholzer, F. Aurenhammer, P. Brass, and H. Krasser. Pseudo-triangulations from surfaces and a novel type of edge flip. SIAM Journal on Computing, 32:1621-1653, 2003.