Constrained Triangulation of a Convex Polytope

Question

Hi,

I am looking for an algorithm that can do a constrained triangulation of a convex polytope (nDimensional). The constraint is that it should contain certain n-1Dimensional simplicies. Can someone recommend a paper, or at least a paper that does this in an unconstrained way? I am not interested in any properties of the triangulation (Delaunay - too complicated for my problem) and no points should be inserted.

Thanks

Answer 1

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.

           
           _{(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.

Answer 2

Thanks for your answer! What is the situation like if I have a Ndim polytope that I want to triangulate and my constraint is that it that its N-simplicies should contain certain N-1-simplicies? For example, in 3D, I want the triangulation of the polyhedron to contain certain triangles.