列出四面体的所有有趣部分

Question

答案更新,12/22:使用Peter Shor 观察到立方体上不同部分和对象排列之间存在同态,通过将一组立方体对称性表示为SymmetricGroup [8]的子组并使用GroupElements/Permute列出所有这些排列,发现使用Mathematica的SAT求解器质心的任务,选择不同的定奇异值,一些更为详细的,完整的代码点集合在这里

题

有趣的2D截面是穿过常规3D 单形和其他2个点的中心的平面,每个点都是一些非空顶点子集的质心.它由两个顶点子集定义.例如{{1},{1,2}}给出一个由3个点定义的平面 - 四面体的中心,第一个顶点,以及第一个和第二个顶点的平均值.

一组有趣的部分是一个集合,其中没有两个部分在顶点重新标记下定义相同的平面.例如,设置{{{1},{2}},{{3},{4}}}并不有趣.有没有一种有效的方法来找到一组有趣的部分？我需要的东西可以推广到7D单形的3D部分的类似问题,并在一夜之间完成.

我的尝试方法如下.一个问题是,如果你忽略几何,一些等效的部分将被保留,所以我得到10个部分而不是3.更大的问题是我使用蛮力并且它肯定不会扩展和(需要10 ^ 17比较7D单纯形)

http://yaroslavvb.com/upload/simplex-sections.png

这是上面生成图片的Mathematica代码.

entropy[vec_] := Total[Table[p Log[p], {p, vec}]];
hadamard = KroneckerProduct @@ Table[{{1, 1}, {1, -1}}, {2}];
(* rows of hadamard matrix give simplex vertex coordinates *)

vertices = hadamard;
invHad = Inverse[hadamard];
m = {m1, m2, m3, m4};
vs = Range[4];

(* take a set of vertex averages, generate all combinations arising \
from labeling of vertices *)
vertexPermutations[set_] := (
   newSets = set /. Thread[vs -> #] & /@ Permutations[vs];
   Map[Sort, newSets, {2}]
   );
(* anchors used to define a section plane *)

sectionAnchors = Subsets[{1, 2, 3, 4}, {1, 3}];
(* all sets of anchor combinations with centroid anchor always \
included *)
anchorSets = Subsets[sectionAnchors, {2}];
anchorSets = Prepend[#, {1, 2, 3, 4}] & /@ anchorSets;
anchorSets = Map[Sort, anchorSets, {2}];
setEquivalent[set1_, set2_] := MemberQ[vertexPermutations[set1], set2];
equivalenceMatrix = 
  Table[Boole[setEquivalent[set1, set2]], {set1, anchorSets}, {set2, 
    anchorSets}];
Needs["GraphUtilities`"];
(* Representatives of "vertex-relabeling" equivalence classes of \
ancher sets *)
reps = First /@ StrongComponents[equivalenceMatrix];

average[verts_] := Total[vertices[[#]] & /@ verts]/Length[verts];
makeSection2D[vars_, {p0_, p1_, p2_}] := Module[{},
   v1 = p1 - p0 // Normalize;
   v2 = p2 - p0;
   v2 = v2 - (v1.v2) v1 // Normalize;
   Thread[vars -> (p0 + v1 x + v2 y)]
   ];

plotSection2D[f_, pointset_] := (
   simplex = 
    Graphics3D[{Yellow, Opacity[.2], 
      GraphicsComplex[Transpose@Rest@hadamard, 
       Polygon[Subsets[{1, 2, 3, 4}, {3}]]]}];
   anchors = average /@ pointset;
   section = makeSection2D[m, anchors];
   rf = Function @@ ({{x, y, z, u, v}, 
       And @@ Thread[invHad.{1, x, y, z} > 0]});
   mf = Function @@ {{p1, p2, p3, x, y}, f[invHad.m /. section]};
   sectionPlot = 
    ParametricPlot3D @@ {Rest[m] /. section, {x, -3, 3}, {y, -3, 3}, 
      RegionFunction -> rf, MeshFunctions -> {mf}};
   anchorPlot = Graphics3D[Sphere[Rest[#], .05] & /@ anchors];
   Show[simplex, sectionPlot, anchorPlot]
   );
plots = Table[
   plotSection2D[entropy, anchorSets[[rep]]], {rep, reps}];
GraphicsGrid[Partition[plots, 3]]

Answer 1

正确的编程解决方案概述如下：

• 观察中心以投影对的形式出现——因此识别并仅保留位于一组中心的一个或另一个半球形覆盖物中的一半中心。配对是彼此互补的。示例规则：包含顶点 1 的所有子集，以及“赤道”上的子集，包含顶点 2 的子集，以及该集合的“赤道”上包含顶点 3 的子集，依此类推，递归地保持边界一半与最小索引相邻顶点。
• 观察到对于每个子单纯形，子单纯形要么与顶点 1 相邻，要么距单纯形距离 1。（原因：四面体中的每个新顶点都附加到四面体的每个先前顶点 - 因此每个子单纯形要么入射在顶点 1 上，要么顶点 1 连接到单纯形中的每个顶点。）因此，每个子单纯形中只有两个总体一种次单纯形（相对于指定的顶点）。（我们可以用只保留每个投影对中较小的成员的决定来代替这个观察，但是标记顶点的规则会更加复杂。）

• 四面体在顶点标签排列下是完全对称的。因此，任何“有趣的部分”等价于仅包含顶点的前导段的另一个部分——即可以在某些n的顶点Range[1,n]中被识别。

• 收集以上内容，我们发现存在从有趣部分到一组图的投影。对于每个图，我们必须枚举一致的顶点成员资格（稍后描述）。除一个顶点外，图的顶点都是成对的

  • 该对包含给定基数的所有中心（给定维度的所有子单纯形）。
  • 该对中的一个成员包含入射在顶点 1 上的中心。
  • 该对的另一个成员包含未与顶点 1 重合的中心。
  • 特殊顶点是包含所有顶点的中心或其射影对（“空中心”）。
  • 如果图包含一对中的任何成员，则它必须（至少）包含包含与 1 相关的中心的成员（或者可以重新标记顶点以实现此目的）。
• 图的边缘被加权。权重是两个中心共享的顶点数。基于每端中心的基数以及两个顶点是否都是第一成员、都是第二成员或者都是其中一个，对权重有限制。（例如，“其中一个”不能共享顶点 1。）
• 图是顶点集上的完整子图，包含特殊顶点。例如，对于四面体，图是上面确定的一组顶点上的 K_{3}，其中一个顶点是特殊顶点，并且具有边权重。
• 部分是在每条边末端的中心一致应用标签的图（即，一致地标记以尊重由边的权重指示的共享顶点的数量，并且一组图顶点中的每个子集包含顶点 1） 。因此，给定的图可以表示多个部分（通过不同的标签）。（选项并不像听起来那么多，很快就会明白。）
• 如果由其中心坐标组成的矩阵具有零行列式，则该部分就没有意义。

在具有四个顶点的三个维度的情况下，我们得到以下集合（我们使用短射影对，因为本示例中有足够的可见性，不需要更简单的顶点标记拒绝规则）：
0：{1,2 的射影对,3,4}
1: {1}
1': {2},{3},{4}
2: {1,2},{1,3},{1,4}
2'：到 2 的投影对（因此省略）
3：到 1' 的投影对（因此省略）
3'：到 1 的投影对（因此省略）

标签约束：
{0->x,x}
{0->x',x}
{1->1,1} -- 不允许：中心不包含两次
{1->1',0}
{1-> 2,1}
{2->2,1}
这些图顶点不可能有其他权重。

图是 0 上的 K_{3} 事件，以下图符合图选择规则：
A: {0->1,1},{0->1',1},{1->1',0 }
B: {0->2,2},{0->2,2},{2->2,1}

A 只有一个标签：{1}、{2}、{}，并且是您的三角形有趣集。该标记不具有零行列式。
B 只有一个标签：{1,2}、{1,3}、{}，并且是您的方形有趣集合。该标记不具有零行列式。

转换为代码作为练习留给读者（因为我必须去上班）。