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
    I think you mean a tessellation of $\mathbb{R}^n$ into (congruent?) $n$-simplices. Obviously if we can split an $n$-cube into such pieces, this gives a way to do the whole space.2012-07-25
  • 0
    @hardmath Not sure in terms. As example if given a $\mathbb{R}^{3}$ cube I'd like to tessellate it into tetrahedrons.2012-07-25
  • 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
    Can you provide a generic algorithm? According to your proof I shall start from $(1,1,...,1)$ and create a tree of edges with height $n$ - is it right that each path from root to leave in such tree will form a simplex?2012-07-25
  • 0
    Do you have a lattice of all integer-coordinate points? Your question is somewhat vague about triangulating "the rectangular area in $\mathbb{R}^n$. Do you have one rectangular parallelpiped to be dissected, or did you want to dissect all of $\mathbb{R}^n$ into $n$-simplices?2012-07-25
  • 0
    One more question. The term "triangulate" conventionally means that simplices meet face to face, and the term "dissect" is often used to distinguish the case where simplices (or other figures) cover the given region with disjoint interiors, but do not necessarily meet "face to face". Does this matter for your application?2012-07-25
  • 1
    I have one n-dimension parallelepiped in $\mathbb{R}^{n}$ which is set by integer coordinates of it's vertexes. Simplices shall meet face to face and fill the whole interior of it. Also if't it possible I'd like to avoid simplices which are "thin" - when the length (Euclidean distance) of one edge is much smaller than others.2012-07-25
  • 1
    Sure, give me a bit to explain the tradeoffs on aspect ratios of the simplices. I included a link (in editing your Question) to an explanation of the Delaunay triangulation in $n$-dimensions, but it isn't really a relevant approach because it depends on using an arbitrary set of supplied points inside the region. At best it would be overkill, and potentially it frustrates your desire to minimize the ratios of longest to shortest edges.2012-07-25
  • 0
    I've implemented the approach from your proof to the Ross's answer (Freudenthal's triangulation). Before triangulation I transform a parallelepiped into the cube. There's still an open question if simplices will be "skinny" after reverse transformation. Is there a way to modify the algorithm to avoid it?2012-07-26
  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/4246/discussion-between-andrey-ermakov-and-hardmath)2012-07-26
  • 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)$

  • 1
    Yep, it does work in higher dimensions. Starting from the origin of the unit $n$-cube $\mathbb{I}^n$, we take any of the $n!$ edge paths of length $n$ that take us to the far corner $(1,1,...,1)$. Each such path involves $n+1$ of the $n$-cube's vertices, and thus generates a simplex. Although such simplices may share faces, etc. (they certainly all share the same $\sqrt{n}$ length edge), their interiors are disjoint. Thus they "triangulate" the hypercube.2012-07-25
  • 0
    @hardmath: Thanks. A neat proof that it works.2012-07-25