Given a polyhedron consists of a list of vertices (v), a list of edges (e), and a list of surfaces connecting those edges (s), how to break the polyhedron into a list of tetrahedron?
I have a convex polyhedron.
[Math] Break polyhedron into tetrahedron
convex-geometryconvex-polytopesmg.metric-geometry
Related Solutions
This is not a definitive answer, just some thoughts. You start with a convex polygon $A$, and displace its vertices by a vector field to produce $B$, connecting corresponding vertices. First, it is not clear that $B$ is necessarily a planar convex polygon, unless you have special conditions on the vector field. $B$ could be nonplanar; $B$ could be nonconvex. So the resulting polyhedron $P$ seems not well defined. You could define $P$ to be the convex hull of $A$ and the vertices of $B$, but then you lose the property that each vertex of $A$ is connected to its corresponding vertex in $B$.
Let me ignore this, and assume that $B$ is a planar convex polygon. Even for $A$ and $B$ triangles, it may be that under one definition of what constitutes $P$, it is not tetrahedralizable. The famous Schönhardt polyhedron is the simplest example:
Image from Discrete and Computational Geometry.
Setting aside both of these issues, which may not occur in your data, there are specialized tetrahedralization algorithms. In fact, you might adapt the definition of $P$ so that these algorithms apply. Here is an incomplete tour through some literature.
Goodman and Pollack showed that the region between two convex polyhedra can be tetrahedralized without "Steiner points," unlike the Schönhardt polyhedron. Marshall Bern then showed that sometimes $\Omega(n^2)$ tetrahedra are needed:
(1) "Compatible tetrahedralizations," Marshall Bern, Proceedings of the 9th Annual Symposium on Computational Geometry, 1993, pp.281-7. Fundam. Inform., 1995: 371-384.
Two subsequent papers studied special cases that are easier: e.g., "slabs" in (2):
(2) "Tetrahedralization of Simple and Non-Simple Polyhedra," Godfried T. Toussaint, Clark Verbrugge, Cao An Wang, Binhai Zhu, Canadian Conference on Computational Geometry, pp. 24-29, 1993.
and a slightly more general case in (3) below. I think this work by Palios may be the most relevant for your purposes, because the case he considers can cover a version of your polyhedra $P$, and because he proves that only $O(n)$ tetrahedra are needed in this case:
(3) Leonidas Palios, "Optimal tetrahedralization of the 3D-region “between” a convex polyhedron and a convex polygon," Computational Geometry, Volume 6, Issue 5, September 1996, Pages 263-276.
Once you have $P$ tetrahedralized, then you can focus on intersecting the tetrahedra with the convex polyhedron.
In $\mathbb{R}^3$ this is a famous problem.See this nice reference. (Danzer, Grunbaum, Shepard -- Does every type of polyhedron tile three-space). The best example at the time of the writing had 38 faces (an example of Engel). For a lattice (periodic) tiling, the problem was solved (I think) by Delone (AKA Delaunay).
Best Answer
If I understand your question correctly, you're saying that the given information is the face structure of a 3-dimensional convex polytope, and you would like a subdivision of the polytope into tetrahedra.
Here is one way to proceed. First, subdivide all the faces into triangles. Then pick your favourite vertex $v_0$. Connect $v_0$ to each triangle belonging to a face not containing $v_0$. This subdivides your polytope into tetrahedra.