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.

  • 1
    $\begingroup$ Context? More information of what you've already tried, or looked at? $\endgroup$ – Yemon Choi Dec 3 '09 at 8:46
  • 5
    $\begingroup$ Can we add additional vertices? It's important, because there are polyhedra which cannot be triangulated into tetrahedra without adding new vertices, such as Schönhardt polyhedron, en.wikipedia.org/wiki/Schönhardt_polyhedron $\endgroup$ – Nurdin Takenov Dec 3 '09 at 12:27
  • $\begingroup$ This seems really homework-y. $\endgroup$ – Harry Gindi Dec 3 '09 at 14:52
  • 1
    $\begingroup$ I have a similar question with a slightly different motivation(maybe). Consider a convex n-polytope given by normal vectors with length determined as the (n-1)-volume of the "faces" and the vectors base point at the "center of mass" of the "faces" in general position. Can one determine the similarly defined normal vectors of the tetrahedrons if we decompose this polytope into (n-1)-tetrahedrons? I hope this short explanation is adequate. If necessary I can move this question to its own thread. $\endgroup$ – B. Bischof Dec 3 '09 at 22:28

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.

  • 3
    $\begingroup$ ...assuming the initial polihedron is convex (which you cannot tell from the combinatorial data alone) $\endgroup$ – Mariano Suárez-Álvarez Dec 3 '09 at 14:49
  • 2
    $\begingroup$ If the initial polyhedron is concave, then it's simple to split it into multiple convex polyhedrons; then just apply the procedure to each faction. $\endgroup$ – Gabriel Benamy Dec 3 '09 at 14:59
  • 1
    $\begingroup$ Not as easy as all that. See the comment to the question by Nurdin Takenov -- if you don't assume convexity, you may have to introduce new vertices. $\endgroup$ – Hugh Thomas Dec 3 '09 at 15:11
  • 1
    $\begingroup$ I saw, but from my understanding of the problem, it's just "list of tetrahedrons". $\endgroup$ – Gabriel Benamy Dec 3 '09 at 15:22
  • $\begingroup$ If the (convex) input polyhedron contains non-triangular faces, then this algorithm could lead to degenerate (zero volume) tetrahedra. Consider if your chosen vertex lies on the same plane as a non-incident triangle. A fix would be to create the triangulation with triangles fans from the chosen vertex for all incident faces. $\endgroup$ – Alec Jacobson May 9 '20 at 23:33

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.

  • Joe Malkevitch

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.