Let $A_1,A_2,A_3 \in \mathbb{N}^3$ be three points in space all lying in some plane $x+y+z=d$ where $d$ is a positive integer. If $\{e_1,e_2,e_3\}$ is the standard basis in $\mathbb{R}^3$, we can construct a polyhedron $$ P = \mathrm{conv}(A_1,A_2,A_3) + \mathrm{cone}(e_1,e_2,e_3) $$ where $\mathrm{conv}$ denotes the convex hull, $\mathrm{cone}$ is the cone, and + is the usual Minkowski sum. We can assume that the $A_i$ are in general position, so that $\mathrm{conv}(A_1,A_2,A_3)$ forms a triangle. There is a nice way to triangulate $P$ without adding new vertices: 1. Choose a distinguished vertex; say $A_1$. 2. Set $L$ to be the facets of $P$ which do not contain $A_1$. 3. If $l \in L$ is a triangle (has three vertices including those at infinity), then take the pyramid over $l$ with vertex $A_1$ and add this polyhedron (a possibly unbounded 3-simplex) to the triangulation. 4. Otherwise, $l$ must be triangulated by the analogous procedure. The problem is that this method requires that I know the face lattice of $P$ beforehand. For 3-polyhedra this seems fine, because I can just look at them, but for the situation in higher dimensions, I'm in trouble. If I have $A = \{A_1, A_2, \dots, A_n\} \subset \mathbb{N}^n$ lying in the plane $x_1 + x_2 + \dots + x_n = d$ and in general position, I'd like to triangulate the polyhedron $$P = \mathrm{conv}(A) + \mathrm{cone}(e_1,\dots,e_n).$$ **Question 1**: Is there a way to construct the face lattice for these polyhedra? **Question 2**: Is there some other way to triangulate these without adding new vertices? The points $A_i$ come from the exponent vectors of monomials in $\mathbb{Z}[z_1,\dots,z_n]$. The polyhedra I've described are certain Newton polyhedra. **Question 3**: Should this additional structure play a role in this problem some how? For instance, the polyhedron $P$ is _not_ the cone coming from the semigroup generated by the $A_i$.