# Regular Triangulations of Cube

I want to figure out which triangulations of the cube (i.e., partitions into tetrahedra using only the $8$ given vertices) are regular, but I'm not sure how to easily tell whether a given triangulation is regular. Is there some condition I can check relatively quickly to see if a particular triangulation is regular?

Edit: A triangulation of the cube is regular if there exists a convex piecewise-linear function from the cube to $\mathbb R$ such that the projection of the boundaries of the regions of linearity onto the cube gives the triangulation.

• What do you mean by "regular triangulation" (there are many meanings for the adjective "regular" in mathematics...)? Jan 31 '16 at 15:49
• I edited my question. Jan 31 '16 at 15:58
• Sorry. Still not clear for me; 1) what do you mean by "the cube" ? Its surface ? 2) could you give an example of such a function ; it is difficult to figure out what are they, and what are they for. Jan 31 '16 at 16:06
• I mean the surface and interior. I'll give an example for a $2$-dimensional triangulation: say you have the square $[0, 1]^2$ and draw it's positive slope diagonal. Consider the convex function that equals $1$ when $x+y\leq 1$ and $2-x-y$ when $x+y\geq 1$. This is a convex piecewise linear function on the square. The boundary between its two pieces is the diagonal of the domain, which means this triangulation is regular. Jan 31 '16 at 16:09
• Now that the issue is clear, are you asking, for a given triangulation, about the existence or non existence of such a function ? In the case of non existence, it looks rather hard,no ? Jan 31 '16 at 16:27

I have no solution at present, but I think that turning to barycentric coordinates (or tetrahedral coordinates) would be very beneficial. This system is used by two applied maths communities: "finite elements computing" and - increasingly - "computer graphism".

It means converting the cartesian formulation (x,y,z) into a formulation with (a,b,c,d) (normalized by $a+b+c+d=1$ that can be given a physical interpretation as "weights").

What is their principle? Being given a point M inside (or outside) ABCD, its barycentric (or tetrahedral) coordinates are the (unique!) (a,b,c,d)=(a,b,c,1-a-b-c) such that M is the weighted average of $A$ with weight $a$, $B$ with weight $b$... This is written: M=aA+bB+cC+dD;

This could be done either by fixing a reference tetrahedron and computing all with respect to it, or define a system of barycentric coordinates with respect to each tetrahedron of your "tetrahedrization" ; Barycentric coordinates behave well with respect to linearity and convexity.

3 references among many:

A nice presentation that can be found on the internet : Cupisz_Robert_Light_Probe_Interpolation.pdf

A lot of pointers can be found in : https://gist.github.com/paniq/8bdec20d00d08810f081

See also the article: "Barycentric coordinates for convex sets" by Warren, Schaefer, Hirani, Desbrun, in Advances in Computational Mathematics (2007) 27: 319-338

Telling whether a given triangulation is regular amounts to feasibility of a certain linear program: your variables are the values of the piece-wise linear function at the vertices. Inequalities express the fact that linearly interpolating the values at vertices on each simplex of your given triangulation the result is a convex function. There is one such inequality for each pair of adjacent tetrahedra.

A more combinatorial sufficient (but not always necessary) condition is that all lexicographic triangulations are regular. It turns out that all triangulations of the 3-cube are lexicographic, hence they are all regular. The same is not true for the $4$-cube.

Some references: both the chapter on Triangulations from the Handbook of Discrete and Computational Geometry, and my book on triangulations both have a section on triangulations of cubes.