Pseudo-tetrahedral complexes

F. Aurenhammer and H. Krasser


Pseudo-triangulations are interesting and flexible generalizations of triangulations that have found their place in computational geometry. Unlike triangulations, pseudo-triangulations eluded a meaningful generalization to higher dimensions so far. In this paper, we define pseudo-simplices and pseudo-simplicial complexes in d-space in a way consistent to pseudo-triangulations in the plane. Flip operations in pseudo-complexes are specified, as combinations of flips in pseudo-triangulations, and of bistellar flips in simplicial complexes. Our results are based on the concept of maximal locally convex functions on polyhedral domains, that allows us to unify several well-known structures, namely pseudo-triangulations, constrained Delaunay triangulations, and regular simplicial complexes.

Reference: F. Aurenhammer and H. Krasser. Pseudo-tetrahedral complexes. In Proc. $21^{st}$ European Workshop on Computational Geometry EuroCG '05, pages 85-88, Eindhoven, The Netherlands, 2005.