Return to Question

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,v5,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

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

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

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,v5,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

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)

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

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