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


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.


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.

  • $\begingroup$ There is actually some more structure in my problem. The points are "reduced" in a certain sense, so that if they are written as the columns of an $n \times n$ matrix, each row must have a zero. As well, the determinant of this matrix must be $d$ (same $d$ as in the question above). Does this help? $\endgroup$ – Corey Harris Feb 18 '15 at 1:16
  • $\begingroup$ Hm, I think I am going to edit my original answer... $\endgroup$ – Francisco Santos Feb 19 '15 at 9:06

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:

  • 1
    $\begingroup$ Thanks, I have some similar pictures for the $\mathbb{R}^3$ case on the arXiv. Is there an effective way to visualize what's happening in $\mathbb{R}^4$? $\endgroup$ – Corey Harris Feb 18 '15 at 1:05
  • $\begingroup$ @CoreyHarris: Nice figures in your paper! For 4D, I think that slicing $P$ with 3-flats parallel to the $A$-simplex could give insight. $\endgroup$ – Joseph O'Rourke Feb 18 '15 at 1:24

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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