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$.