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.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Context? More information of what you've already tried, or looked at? $\endgroup$– Yemon ChoiCommented Dec 3, 2009 at 8:46
-
7$\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 TakenovCommented Dec 3, 2009 at 12:27
-
1$\begingroup$ This seems really homework-y. $\endgroup$– Harry GindiCommented Dec 3, 2009 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. BischofCommented Dec 3, 2009 at 22:28
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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$ Commented Dec 3, 2009 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$ Commented Dec 3, 2009 at 14:59
-
2$\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$ Commented Dec 3, 2009 at 15:11
-
1$\begingroup$ I saw, but from my understanding of the problem, it's just "list of tetrahedrons". $\endgroup$ Commented Dec 3, 2009 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$ Commented May 9, 2020 at 23:33
$\begingroup$
$\endgroup$
1
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
answered Dec 3, 2009 at 15:57