MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to divide a n dimensional simplex (convex hull of n+1 points) in n+1 parts. E.g. consider the simplex in 2-D which is the convex hull of points (0,0,1), (0,1,0) amd (1,0,0). It can be divided in three parts as $P_1 = \{(0,1,0),(1/2,1/2,0),(0,1/2,1/2),(1/3,1/3,1/3)\}$

$P_2 = \{(1,0,0),(1/2,1/2,,0),(1/2,0,1/2),(1/3,1/3,1/3)\}$

$P_3 = \{(0,0,1),(1/2,0,1/2),(0,1/2,1/2),(1/3,1/3,1/3)\}$

I can somehow arrive at these partitions by considering intersection of some halfspaces (line joining the vertex to the midpoint of the other side). However, I am unable to extend this to higher dimensions.

Is there an algorithm in literature which does the same partitions. Can someone point me to some reference.


share|cite|improve this question

closed as off topic by Andrej Bauer, Ryan Budney, Igor Pak, Andy Putman, Dan Petersen Nov 23 '12 at 8:34

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

You're looking for "Voronoi cells" :-) – Gjergji Zaimi Nov 22 '12 at 23:59
This is not a research level question. – Andrej Bauer Nov 23 '12 at 0:07
up vote 2 down vote accepted

In fact, there are much more such divisions. The group of simplex is $S_{n+1}$, so it contains a subgroup $H=\langle (123\dots n+1)\rangle$ of order $n+1$ acting transitively on the hyperfaces. Now take a ray $r$ from the center $O$ of the simplex, and let $\{r_1,\dots,r_{n+1}\}$ be its orbit under the action of $H$. Every $n$ of these rays generate a polyhedral cone, the union of these cones is the whole space (unless something degenerates), and $H$ permutes these cones transitively. Hence $H$ also permutes the intersections of these cones with the simplex, and they are congruent. So, we obtain a desired division.

The pictures below show two types of such divsion of a regular tetrahedron.

two divisions of a tetrahedron

share|cite|improve this answer

The magic word is "barycenter". The convex hull of the barycenter and any one face of the simplex has the right volume.

share|cite|improve this answer
just look up barycentric subdivision please before you start second guessing the answer. It is what you want. – Andrej Bauer Nov 23 '12 at 0:07

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