Pseudo-Triangulations from Surfaces and a Novel Type of Edge Flip
O. Aichholzer, F. Aurenhammer, P. Brass, and H. Krasser
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.