On triangulations of polyhedra, monotone sequences of flips, and decompisitions of 3d embedded prismatoids

A fundamental fact exploited in computational geometry is that one can actually flip between regular triangulations monotonically, in a generalization of what happens for Lawson’s result in the planar Delaunay triangulation. However, the same is not true for non-regular triangulations, in dimensions three and higher. Many of the differences come from the following: Every non-convex polygon in the plane can be triangulated without extra vertices. In contrast, in dimension three (or higher) there are non-triangulable non-convex polytopes, such as the Schoenhardt polyhedron (a twised non-convex prism).

In this talk, we will exploit a nice geometric relation between monotone sequences of flips and triangulations of polyhedra. It explains why Lawson's flip algorithm works and why it may fail in higher dimensions. We then focus on a decomposiotn problem of a class of simple polyhedra – 3d embedded prismatoids. I will show a basic geometric fact on whetehr a decompsotion exists or not. Finally, I will show some related topics to this fact.