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.
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.
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.
There are polyhedra which are homeomorphic to a sphere with the property that every edge which is not already an edge of the polyhedron lies completely in the exterior of the polyhedron. Sometimes these polyhedra are called Lennes Polyhedra. These polyhedra can not be subdivided into tetrahedra using existing vertices of the polyhedron. In the plane, any simple plane polygon can be triangulated. This forms the basis for Steve Fisk's elegant result about "guarding" plane simple polygons. The analogue of this can not be carried out for 3-dimensional polyhedra. For a brief discussion of Lennes Polyhedra see pages. 253 and 254 of J. O'Rourke, Art Gallery Theorems and Algorithms.