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.



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.


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.

  • $\begingroup$ I believe the situation is essentially the same as in my answer: Sometimes the triangulation cannot be completed; it is NP-complete to determine if the triangulation can be completed; and likely bistellar flips might lead to a reasonable algorithm. $\endgroup$ – Joseph O'Rourke Apr 10 '13 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.