3
$\begingroup$

I need to triangulate the n-dimensioned rectangular parallelepiped in $\mathbb{R}^{n}$ into a set of $n$-simplices.

Could you suggest me any known algorithm for that or maybe an extension of Delaunay triangulation for $n > 2$ cases?

  • 0
    An [$n$-simplex](http://en.wikipedia.org/wiki/Simplex) is the convex closure of $n+1$ points not lying in a common $n-1$ dimensional affine hyperplane. Thus a $3$-simplex is a tetrahedron, whose 4 vertices do not lie in a common plane.2012-07-25

2 Answers 2

4

The construction outlined by Ross suffices to dissect an $n$-cube into $n!$ congruent $n$-simplices known as Schläfli orthoschemes.

One might ask if $n!$ is the smallest number of simplexes needed to dissect an $n$-cube, and it is not in general. For example the $3$-cube may be dissected into as few as five tetrahedra (not all congruent). See Lower Bounds for the Simplexity of the $n$-Cube. The exact minimum number needed to dissect a $4$-cube is known to be 16 rather than 24 = 4!.

  • 0
    @AndreyErmakov: I hope you've looked over the chat remarks I left.2012-07-27
2

We can consider cubes, as you can stretch each dimension as you wish. In $\mathbb R^3$, consider the unit cube in the first octant. Triangulate each face that touches the origin, then connect the three corners of each triangle to $(1,1,1)$. This gives a decomposition into six tetrahedra. One of them has corners $(0,0,0), (0,1,0), (1,1,0), (1,1,1)$

I think the same thing works in higher dimensions. Decompose the faces that touch the origin as $n-1$ boxes, then connect all the corners to $(1,1,\ldots ,1)$ The corresponding one in $\mathbb R^4$ to the above example would be $(0,0,0,0), (1,0,0,0), (1,1,0,0), (1,1,1,0), (1,1,1,1)$

  • 0
    @hardmath: Thanks. A neat proof that it works.2012-07-25