TY - JOUR
T1 - Pseudotriangulations from surfaces and a novel type of edge flip
AU - Aichholzer, Oswin
AU - Aurenhammer, Franz
AU - Krasser, Hannes
AU - Brass, Peter
PY - 2003/9
Y1 - 2003/9
N2 - 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.
AB - 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.
KW - Constrained regular complex
KW - Flip distance
KW - Locally convex function
KW - Polytope representation
KW - Pseudotriangulation
KW - Surface realization
KW - Discrete and Computational Geometry
UR - http://www.scopus.com/inward/record.url?scp=0942266548&partnerID=8YFLogxK
U2 - 10.1137/S0097539702411368
DO - 10.1137/S0097539702411368
M3 - Review article
AN - SCOPUS:0942266548
SN - 0097-5397
VL - 32
SP - 1621
EP - 1653
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 6
ER -