I have a doubt on Freudenthal Triangulation. I want to partition a simplex into finer simplices.

The FT gives me the vertices of the simplices which partition my original simplex into finer simplices.

I am interested in enumerating over each of the simplices obtained from the FT algorithm.

However, I am not able to conclude that given the vertices, how do I construct the dividing simplices out of them. In other words, if the vertices are given to me then how can I find which of these vertices make one of the simplices (that partitioned the original simplex)

A brief note on Freudenthal Triangulation using an example (taken from section 4.2 in Lovejoy, W. S. (1991). Computationally feasible bounds for partially observed Markov decision processes. Operations Research, 39(1), 162–175.):

Let us consider an example in $R^3$. We want to triangulate the simplex $$ \Pi(s)= \{\pi \in R^3:\pi_i \ge 0,,i=1,2,3 \sum_{i=1}^3 \pi_i=1 \}$$ We first triangulate the $R^3$ and then by some mapping induce a triangulation in $\Pi(s)$.

To Triangulate $R^3$, consider a constant $M$ and the set of vertices $$G'=\{(q_1,q_2,q_3):M=q_1\ge q_2 \ge q_3 \ge 0\}$$. Also define the non-singular matrix $$B=\frac{1}{M} \begin{pmatrix} 1 & -1 & 0 \\\ 0 & 1 & -1 \\\ 0 & 0 & 1 \end{pmatrix}$$ For $q \in G', Bq = \frac{1}{M} (M-q_2,q_2-q_3,q_3), Bq \in G$ where $$G = \{\frac{m}{M}| m \in I_+^3, \sum m_i = M\}$$ where $I_+^3$ is the set of positive integers. The set $G$ is called the set of regular grid points in $\Pi(s)$. As I said before we triangulate $R^3$ get the vertices in set $G'$ and then transform them to the vertices of set $G$. consider the following example:

The freudenthal triangulation in $R^3$ with M =2 will give us the vertices (basically the set $G'$) as $(2,0,0), (2,2,0), (2,2,2), (2,1,0), (2,1,1), (2,2,1)$ . The vertex in the set $G$ are $v_1 = (1,0,0), v_2 = (0,1,0), v_3 = (0,0,1), v_4 = (0.5,0.5,0), v_5 =(0.5,0,0.5)$ and $v_6 = (0,0.5,0.5)$. The ordering is restored with the transformation, i.e., $(2,0,0)$ refers to $1,0,0$.

My concern is that given the vertices v1,..,v6, how do I arrive at those 4 sub-simplices. I need it as I will be dealing with higher dimensions and finding the sub-simplices may not be that obvious in those cases.

I believe it might be a simple question with simple solution but I am not able to figure it out. I also think that there might be some order in which the vertices are generated and may correspond with vertices of the simplices in the partition. Can you please point me to some reference.

Thank You

  • $\begingroup$ Could you be a little more specific as to what you're talking about? A Google search on "Freudenthal Triangularization" returns this link as the only exact match. $\endgroup$ – Ryan Budney Oct 22 '12 at 22:30
  • $\begingroup$ I am sorry it should be Freudenthal Triangulation. A good discussion on Freudenthal triangulation is given in the paper Lovejoy, W. S. (1991). Computationally feasible bounds for partially observed Markov decision processes. Operations Research, 39(1), 162–175. Anyways, FT gives you a set of vertices (of some simplices) which partition a given simplex. My concern is how can I find out the simplices out of those vertices. $\endgroup$ – user27396 Oct 22 '12 at 22:49
  • $\begingroup$ I also added an example. $\endgroup$ – user27396 Oct 22 '12 at 22:55
  • $\begingroup$ Aren't v1,v2,v5 colinear? Do you mean instead (v1,v5,v6), (v2,v4,v5),(v3,v4,v6) and (v4,v5,v6)? It seems like there are 4 different triangulations with this set of vertices, of which this is one. $\endgroup$ – Patricia Hersh Oct 23 '12 at 4:20
  • $\begingroup$ You are right. Sorry for the mistake. $\endgroup$ – user27396 Oct 23 '12 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.