# Split $n$-dimensional prism into simplices

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)?

Extra question: Is it possible to do the same for cartesian product of two triangles (here is a graph of such structure):

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 <= Length[fl], i++,
For[j = 1, j <= 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]]) &&
i != j, AppendTo[edges, fl[[i]] <-> fl[[j]]]]
];
];
F1 = Graph[DeleteDuplicates[Sort /@ edges]];
Graph[F1, VertexLabels -> "Name"]

• What is the range of n? If it is 1, 2 or 3 then ConvexHullMesh might do what you want. In the more general case: If the base is already divided into simplices then the task can be reduced to splitting a simplicial prism... – Henrik Schumacher Feb 6 '18 at 9:32
• @HenrikSchumacher n is 6. I was wondering if there is something like geometry computations that would allow to add and subtract one general geometry from another. Base is a simplex. – Vsevolod A. Feb 6 '18 at 13:34

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:

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}]]


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.

If you have $k>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. EDIT 1: 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 Proposition 25 here, but only because of the word "prism"): For a simplex $S_1$ times another simplex $S_2$, the natural (to me) generalization seems to be to take all north-east lattice paths on the grid of vertices $S_1\times S_2$. For example, if $S_1$ and $S_2$ are both 3-dimensional: 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).

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.

EDIT 2: 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 this answer.

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 -> "Name"];
Paths = FindPath[g, 1, dim1*dim2, dim1 + dim2 - 2, All];
Table[Table[L1xL2[[i]], {i, P}], {P, Paths}]];


Here L1 is a list of $k+1$ $k$-tuples and L2 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).

{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}]}]


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 True, it means all pairs are disjoint.

• That was really cool, thanks. Do you think something as simple can be applied to splitting cartesian product of two simplices? – Vsevolod A. Feb 8 '18 at 8:57
• @VsevolodA. can you give me an example of a "cartesian product of two simplices" in your context (maybe as a Mathematica object)? If your prism is $B\times I$, where $B$ is your base and $I=[0,1]$, then using the vertices of $B$ as the input to the function I described should work. – Jānis Lazovskis Feb 8 '18 at 14:33
• That's right, however it's $B\times B$, where $B$ is a triange (or tetrahedron). I added graph of such object to the question. – Vsevolod A. Feb 8 '18 at 15:58
• @VsevolodA. I edited my question to reflect your example, although without Mathematica code, because it is beyond my skill level. – Jānis Lazovskis Feb 10 '18 at 15:19