Constrained Triangulation of a Convex Polytope 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 
 A: 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.
A: 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.
