Skip to main content
4 of 5
replaced http://upload.wikimedia.org/ with https://upload.wikimedia.org/

Once you have pre-specified some simplices $S$ that must be included in your triangulation of the convex polytope $P$, what remains is the problem of triangulating a nonconvex region: $P \setminus S$. There are nonconvex polyhedra (in dimension 3) that cannot be triangulated. I believe one could make such an example from the Schönhardt polyhedron, by insisting on the inclusion of three tetrahedra ($S$) external to that polyhedron as part of a triangulation of the convex hull ($P$) of two twisted triangles in parallel planes, so that $P \setminus S$ is the un-tetrahedralizable Schönhardt polyhedron (see below). And it is an NP-complete problem to decide if a given nonconvex polyhedron can be triangulated, a 1992 result of Ruppert and Seidel.

           alt text
           (Image from Wikipedia)

If you want to nevertheless hope that your region can be triangulated, you might explore geometric bistellar flips to underlie an approach.

Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958