Split $n$-dimensional prism into simplices - Mathematica Stack Exchange most recent 30 from mathematica.stackexchange.com 2019-10-15T22:14:28Z https://mathematica.stackexchange.com/feeds/question/165223 https://creativecommons.org/licenses/by-sa/4.0/rdf https://mathematica.stackexchange.com/q/165223 5 Split $n$-dimensional prism into simplices Vsevolod A. https://mathematica.stackexchange.com/users/51665 2018-02-05T16:58:50Z 2018-02-16T17:44:37Z <p>Are there standard geometry or graph functions that allow to, say, construct a $n$-dimensional prism by it's $(n-1)D$ base and height and split it into simplices (without creating new points)?</p> <p>Extra question: Is it possible to do the same for cartesian product of two triangles (here is a graph of such structure):</p> <pre><code>a = CompleteGraph; b = CompleteGraph; at = Table[Subscript[VertexList[a][[i]],A], {i, 1, Length[VertexList[a]]}]; bt = Table[Subscript[VertexList[b][[i]],B], {i, 1, Length[VertexList[b]]}]; fl = Flatten[ Table[at[[i]] bt[[j]], {i, 1, Length[VertexList[a]]}, {j, 1, Length[VertexList[b]]}]]; edges = {}; For[i = 1, i &lt;= Length[fl], i++, For[j = 1, j &lt;= Length[fl], j++, If[(fl[[i, 1]] == fl[[j, 1]] || fl[[i, 1]] == fl[[j, 2]] || fl[[i, 2]] == fl[[j, 1]] || fl[[i, 2]] == fl[[j, 2]]) &amp;&amp; i != j, AppendTo[edges, fl[[i]] &lt;-&gt; fl[[j]]]] ]; ]; F1 = Graph[DeleteDuplicates[Sort /@ edges]]; Graph[F1, VertexLabels -&gt; "Name"] </code></pre> https://mathematica.stackexchange.com/questions/165223/-/165371#165371 4 Answer by Jānis Lazovskis for Split $n$-dimensional prism into simplices Jānis Lazovskis https://mathematica.stackexchange.com/users/2483 2018-02-07T15:52:33Z 2018-02-16T17:44:37Z <p>First suppose you have $n$ points in $(n-1)$-dimensional vector space in general position (their span is the whole $(n-1)$-dimensional space) as your base. You can get $n$ simplices (I'm using lists of vectors instead of actual simplices) of dimension $n$ from the prism based at these $n$ points and extruded up into the $n$th dimension in the following way:</p> <pre><code>SimplexPrismSplit[PList_] := Module[{dim = Length[PList]}, PBase = Table[Join[PList[[k]], {0}], {k, 1, dim}]; PTop = Table[Join[PList[[k]], {1}], {k, 1, dim}]; Table[Union[Take[PBase, {1, k}], Take[PTop, {k, dim}]], {k, 1, dim}]] </code></pre> <p>I've assumed the base is situated in $n$-space with $0$ as its $n$th coordinate, and the top of the prism with $1$ as its $n$th coordinate.</p> <p>If you have $k&gt;n$ points as your base, choose an "appropriate" collection of subsets of size $n$ and then proceed as above. By "appropriate" I mean split up the base into $k-n+1$ disjoint smaller bases each defined by $n$ points. I'm not sure how to tell Mathematica how to do this "appropriate" step, but that's the intuition. For example, if $n=3$, you want to split up your polygonal base into smaller bases, each of which is a triangle, as below.</p> <p><a href="https://i.stack.imgur.com/oEIrO.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/oEIrO.png" alt="enter image description here"></a></p> <hr> <p><strong>EDIT 1:</strong> Given the example, there is a bit more going on that I can try to explain, but I'm not sure how to code it. For a prism, a base $B=\{a,b,c\}$ times the interval $I=\{0,1\}$, this is how the simplices were chosen (my intuition was only coming from the proof of the functoriality of singular homology, as in <a href="http://math.arizona.edu/~glickenstein/math534_1011/homology.pdf" rel="nofollow noreferrer">Proposition 25 here</a>, but only because of the word "prism"): </p> <p><a href="https://i.stack.imgur.com/n5kBF.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/n5kBF.jpg" alt="enter image description here"></a></p> <p>For a simplex $S_1$ times another simplex $S_2$, the natural (to me) generalization seems to be to take all north-east <a href="https://en.wikipedia.org/wiki/Lattice_path" rel="nofollow noreferrer">lattice paths</a> on the grid of vertices $S_1\times S_2$. For example, if $S_1$ and $S_2$ are both 3-dimensional:</p> <p><a href="https://i.stack.imgur.com/OycYz.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/OycYz.jpg" alt="enter image description here"></a></p> <p>Dimension counting works out (if $\dim(S_1)=k$ and $\dim(S_2)=\ell$, then the dimension of the product is $k+\ell$, as is the dimension of a simplex defined by every north-east lattice path). It also makes some topological sense, as all simplices made in such a way share a face of dimension $k+\ell-1$ (as we are changing one vertex at a time). </p> <p>Hopefully that gives you some intuition on how to make an algorithm that finds all such paths. I would actually guess Mathematica has such a built-in function, I am just too uninformed to know how to look for it.</p> <hr> <p><strong>EDIT 2:</strong> For posterity, here is the code that gives dimension $k+\ell$ simplices in the product of a $k$-simplex with an $\ell$-simplex, borrowing from <a href="https://mathematica.stackexchange.com/questions/112395/how-to-draw-all-paths-from-1-1-to-n-n-by-move-1-0-or-0-1/112411#112411">this answer</a>.</p> <pre><code>SplitProduct[L1_, L2_] := Module[{dim1 = Length[L1], dim2 = Length[L2]}, L1xL2 = Flatten[ Table[Join[L1[[i]], L2[[j]]], {j, 1, dim2}, {i, 1, dim1}], 1]; g = GridGraph[{dim1, dim2}, VertexLabels -&gt; "Name"]; Paths = FindPath[g, 1, dim1*dim2, dim1 + dim2 - 2, All]; Table[Table[L1xL2[[i]], {i, P}], {P, Paths}]]; </code></pre> <p>Here <code>L1</code> is a list of $k+1$ $k$-tuples and <code>L2</code> is a list of $\ell+1$ $\ell$-tuples. I don't have a convincing argument of why every point in the product is contained in a simplex that the code produces. However, the following code shows that all the simplices are disjoint (thanks to @VsevolodA).</p> <pre><code>{k, l} = {3, 3}; S1 = RandomReal[{-1, 1}, {k + 1, k}]; S2 = RandomReal[{-1, 1}, {l + 1, l}]; Simplices = SplitProduct[S1, S2]; RandVec = Table[0.0000001 RandomReal[{-1, 1}, k + l], {i, 1, k + l}]; Table[Fold[Or, Table[RegionDisjoint[Simplex[pair[]], Simplex[Table[w + v, {w, pair[]}]]], {v, RandVec}]], {pair, Subsets[Simplices, {2}]}] </code></pre> <p>The code slightly budges a simplex in random directions, and if at least one of them gives a completely disjoint pair, then they only share a lower-dimensional face, as desired. So if the code returns a list of <code>True</code>, it means all pairs are disjoint.</p>