3
$\begingroup$

First using a three dimensional unit cube as an example for the term "regularity", we can have two possible triangulations:

(A)A

(B)B

We say the lower triangulation is more "regular" than upper triangulation in that the following ratio for each simplex $K$ varies less among all the simplices: $$ \alpha_K = \frac{\rho_K}{r_K}, \tag{1} $$ where $\rho_K$ is the radius of the inscribed sphere for a simplex $K$, and $r_K$ is the radius of the circumscribed sphere.

If a triangulation is more regular than another, then after a local refinement using "irregular cuts", say, longest edge bisection for each simplex for both triangulations, we are more likely to get an equal regular triangulation for a more regular triangulation (like B) than a less regular triangulation (like A).

A "regular cut" is something like octasection of a tetrahedron by connecting the midpoints of each edge to get $2^3$ similar tetrahedra, just smaller. An "irregular cut" is like following:

cut

in that a simplex is only being divided into 2 smaller simplices. The following figure shows the result of bisecting using the longest edges for all tetrahedra for B(left) and A(right):

bisecting

For the longest edges varies for triangulation A, to keep the subdivision as a triangulation (no hanging vertices), we need to subdivide more. Needless to say which one is more regular.

When going into four dimensions, things get quite nasty. I am developing an automated mesh generation library for 4-manifold (say we already know that this manifold has piecewise linear structure, and is triangulable), I found that I simply can not afford "regular cut" for the triangulation. I will get $2^4$ smaller 4-simplices from just one 4-simplex, and the computer runs out of memory pretty fast during refining. Hence I could only afford local refinement using "irregular cuts".

For 4D triangulation, if using Whitney's trick, then 4-manifolds is divided into hypercubical lattices, then each cube is triangulated into 4-simplices. I wanna avoid to get the triangulation like (A) but rather to have triangulation like (B).

Finally my question is: how to triangulate a hypercube resembling (B)? in the sense that, after bisecting the longest edge for a 4-simplex (and its neighboring simplices), the regularity of the mesh does not change too much in terms of the ratio in (1).

Any reference is welcome too.

Improve this question
$\endgroup$
2
  • $\begingroup$ Perhaps you are already familiar with the notion of a fat triangulation, in which the circum-to-inradius ratio of each simplex is bounded by a constant. Fat triangulations are candidates for your type of regularity. (And note that "regular triangulations" are yet a different concept.) $\endgroup$
    – Joseph O'Rourke
    Commented May 16, 2013 at 23:42
  • $\begingroup$ @JosephO'Rourke Thanks for the heads up, I know fat triangulation is good, but somehow I only managed to implement it in dimension 2 geometry... $\endgroup$
    – Shuhao Cao
    Commented Jun 25, 2013 at 15:14

1 Answer 1

Reset to default
6
$\begingroup$

"Finally my question is: how to triangulate a hypercube resembling (B)?"

This is easy to do, and is normally called the "standard triangulation" of the $n$-cube. Consider all the monotone edge paths from $(0,...,0)$ to $(1,...,1)$ (there are $n!$ of them, corresponding to the $n!$ orderings in which you may decide to increase your coordinates along the monotone path). It turns out that taking as simplices the convex hulls of these paths you get a triangulation in which all the simplices are congruent to one another. In particular, the ratio you are interested in is the same in all simplices.

This triangulation has other many nice properties. To name just one, you can obtain it dissecting the hypercube via the $\binom{n}{2}$ hyperplanes of the form $x_i=x_j$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .