Pseudotriangulations from Surfaces and a Novel Type of Edge Flip
Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, Peter Braß · SIAM Journal on Computing · 2003
We prove that planar pseudotriangulations 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 drastic 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 pseudotriangulations in a natural way.