Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Context? More information of what you've already tried, or looked at? –  Yemon Choi Dec 3 '09 at 8:46
4  
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 –  Nurdin Takenov Dec 3 '09 at 12:27
    
This seems really homework-y. –  Harry Gindi Dec 3 '09 at 14:52
    
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. –  B. Bischof Dec 3 '09 at 22:28

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
1  
...assuming the initial polihedron is convex (which you cannot tell from the combinatorial data alone) –  Mariano Suárez-Alvarez Dec 3 '09 at 14:49
1  
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. –  Gabriel Benamy Dec 3 '09 at 14:59
    
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. –  Hugh Thomas Dec 3 '09 at 15:11
    
I saw, but from my understanding of the problem, it's just "list of tetrahedrons". –  Gabriel Benamy Dec 3 '09 at 15:22

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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