Spatial Embedding of Pseudo-Triangulations

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

Abstract:

We show that pseudo-triangulations have natural embeddings in three-space. As a consequence, various concepts for triangulations, like flipping to optimality, (constrained) Delaunayhood, and a polytope representation carry over to pseudo-triangulations.

Reference: O. Aichholzer, F. Aurenhammer, P. Brass, and H. Krasser. Spatial embedding of pseudo-triangulations. In Proc. $19^{th}$ Ann. ACM Symp. Computational Geometry, volume 19, pages 144-153, San Diego, California, USA, 2003.