Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  hardmath Jul 25 '12 at 0:09
    
@hardmath Not sure in terms. As example if given a $\mathbb{R}^{3}$ cube I'd like to tessellate it into tetrahedrons. –  Andrey Ermakov Jul 25 '12 at 0:15
    
An $n$-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. –  hardmath Jul 25 '12 at 0:53

2 Answers 2

up vote 4 down vote accepted

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!.

share|improve this answer
    
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? –  Andrey Ermakov Jul 25 '12 at 11:37
    
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? –  hardmath Jul 25 '12 at 11:42
    
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? –  hardmath Jul 25 '12 at 11:46
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. –  Andrey Ermakov Jul 25 '12 at 11:55
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. –  hardmath Jul 25 '12 at 13:00

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)$

share|improve this answer
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. –  hardmath Jul 25 '12 at 2:36
    
@hardmath: Thanks. A neat proof that it works. –  Ross Millikan Jul 25 '12 at 2:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.