0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ What do you mean by "regular triangulation" (there are many meanings for the adjective "regular" in mathematics...)? $\endgroup$
    – Jean Marie
    Jan 31 '16 at 15:49
  • $\begingroup$ I edited my question. $\endgroup$
    – Nishant
    Jan 31 '16 at 15:58
  • $\begingroup$ 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. $\endgroup$
    – Jean Marie
    Jan 31 '16 at 16:06
  • $\begingroup$ 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. $\endgroup$
    – Nishant
    Jan 31 '16 at 16:09
  • $\begingroup$ 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 ? $\endgroup$
    – Jean Marie
    Jan 31 '16 at 16:27
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.