6 Added an explanation of freudenthal triangulation

For

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 case of three dimensions. A simplex $$\Pi(s)= \{\pi \in 3-D is given as 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 convex hull of triangulation in $\Pi(s)$.

To Triangulate $R^3$, consider a constant $M$ and the set of vertices (0,0,1), ($$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} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 ) and & 0 & 1For q \in G', Bq = \frac{1}{M} (1,0,0). An exemplary FT 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 this example positive integers. The set $G$ is called the simplices 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 v1 (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 = (0,0,1), v2 1,0,0), v_2 = (0,1,0), v3 v_3 = (1,0,0), v4 0,0,1), v_4 = (0.5,0.5,0), v5 v_5 =(0,0.5,0.5) (0.5,0,0.5)$ and v6 $v_6 = (0.5,0,0.5). Not sure how to draw it here but on paper you will see the original simplex (which will be a triangle) divided into 4 sub-triangles 0,0.5,0.5)$. The ordering is restored with the vertices (v1,v5,v6), (v2,v4,v5),(v3,v4,v6) and (v4,v5,v6)transformation, i.e., $(2,0,0)$ refers to $1,0,0$.

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.

5 The example was wrongly presented

HI,

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)

For example consider the case of three dimensions. A simplex in 3-D is given as a convex hull of the vertices (0,0,1), (0 1 0) and (1,0,0). An exemplary FT of this example is the simplices with vertices v1 = (0,0,1), v2 = (0,1,0), v3 = (1,0,0), v4 = (0.5,0.5,0), v5 = (0,0.5,0.5) and v6 = (0.5,0,0.5).

Not sure how to draw it here but on paper you will see the original simplex (which will be a triangle) divided into 4 sub-triangles with the vertices (v1,v2,v5), (v3,v2,v4), v1,v5,v6), (v1,v3,v6) v2,v4,v5),(v3,v4,v6) and (v4,v5,v6)

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. Can you please point me to some reference. Thank You

4 added 729 characters in body

HI,

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)

For example consider the case of three dimensions. A simplex in 3-D is given as a convex hull of the vertices (0,0,1), (0 1 0) and (1,0,0). An exemplary FT of this example is the simplices with vertices v1 = (0,0,1), v2 = (0,1,0), v3 = (1,0,0), v4 = (0.5,0.5,0), v5 = (0,0.5,0.5) and v6 = (0.5,0,0.5).

Not sure how to draw it here but on paper you will see the original simplex (which will be a triangle) divided into 4 sub-triangles with the vertices (v1,v2,v5), (v3,v2,v4), (v1,v3,v6) and (v4,v5,v6)

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. Can you please point me to some reference. Thank You

3 deleted 4 characters in body
2 edited tags
1