Triangulations of special polyhedra

Question

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

Answer 1

Unless you have some additional structure on the points $A_1$,...,$A_n$ your problem is as hard (and as easy) as computing the convex hull of $2n$ points in $\mathbb{R}^n$, and triangulating this convex hull.

EDIT:

Neither the fact that you have zeroes nor the value of the determinant simplify the problem, as far as I can see.

The way I think about your problem is as follows. Using projective coordinates, you have $2n$ vectors $(A_1,1),\dots, (A_n,1), (e_1,0),\dots, (e_n,0)$ in $\mathbb R^{n+1}$ and want to compute its positive hull and a triangulation (in the sense of vector configurations) of it. If you prefer to live in the affine world, you can multiply the last $n$ vectors by $d+1$ so that all your vectors (now points) lie in the affine space $\sum x_i = d+1$. In this sense, as I said in my original answer, your problem becomes that of computing a convex hull (Q1) and a triangulation (Q2) of $2n$ points in $\mathbb R^n$.

If you are interested in arbitrary $n$ I think there is not much more I can say other than "use the general machinery". But if you are interested in small $n$ there are two things you can do to get a lower dimensional "picture" of your problem:

• Cayley Trick: your configuration is a Cayley configuration, meaning that your $2n$ points lie in two parallel hyperplanes. What the Cayley Trick says is that in these conditions you only need to look at what happens at an intermediate hyperplane, where what you have is a Minkowski sum of two $(n-1)$-simplices. Triangulations of your polytope become (and are in bijection to) fine mixed subdivisions of this Minkowski sum of two $(n-1)$-simplices.

• Gale transform: the Gale transform of $2n$ points in affine $n$-space is $2n$-vectors in $\mathbb R^{n-1}$. In a Gale transform you can "read" both the convex hull and the triangulations of your original polytope.

You can learn more about both aspects in my book on Triangulations (Section 9.2 for the Cayley Trick, Sections 4.1 and 5.4, among others, for Gale transforms and their relation to triangulations.

Answer 2

Not an answer; just an illustration.

I doubt this helps, but here is an indication of what the polyhedron would look like in $\mathbb{R}^3$:

---

         

---

The origin is green, $\{A_1, A_2, A_3\}$ are the three corners of the triangle, and the ribs of $\mathrm{cone}(e_1,e_2,e_3)$ are depicted at each vertex. One then has to imagine extending the ribs to $\infty$ and taking the convex hull. Here is a portion of that hull:

---

         

---