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

18
回答更新,12/22:根据Peter Shor的观察,不同截面之间存在同态映射和立方体上对象排列的置换关系。通过将立方体对称群表示为SymmetricGroup[8]的子群,并使用GroupElements/Permute来列举所有这样的置换,使用Mathematica的SAT求解器找到质心分配,选择具有不同奇异值的点集,给出更多细节和完整代码,请参考此处问题:

一种有趣的2D截面是指穿过正3Dsimplex中心和另外两个点的平面,每个点都是某些非空顶点子集的质心。这由两个顶点子集定义。例如{{1},{1,2}}给出了一个由三个点定义的平面——四面体的中心、第一个顶点和第一个和第二个顶点的平均值。

一组有趣的截面是一组没有两个截面在在重新标记顶点后定义相同平面的截面。例如,集合{{{1},{2}},{{3},{4}}}就不是有趣的。是否有一种有效的方法来找到一组有趣的截面?我需要一些可以推广到7D simplex的3D截面类似问题的方法,并且能在一晚上完成。

我尝试的方法如下。一个问题是如果忽略几何,一些等价的截面将被保留,因此我得到了10个截面而不是3个。更大的问题是我使用了蛮力算法,它绝对不能扩展 (对于7D simplex需要进行10^17个比较)。


(来源:yaroslavvb.com)

这里是生成上图的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]]

我已经尝试了多次去理解{{1},{1,2}}和{{{1},{2}},{{3},{4}}}的符号表示,但是一直无法理解。你能提供一个解释它们的链接吗? - Dialecticus
所以,如果我理解问题正确的话,您需要找到顶点的超集,并获取其中每个集合的质心。然后创建与简单形状的每两个相交的每个平面以及其质心...是这样吗? - JoshD
如果您随意选择顶点,则可能会得到退化的部分。测试共线性很容易,不像枚举非等效的部分(无论是否退化)。 - Yaroslav Bulatov
你是否已经成功解决了这个问题?还需要帮助吗? - jcolebrand
@drachenstern:有一个提议的算法,但看起来很复杂,作者没有提供代码,一些适用于7维的C/Java/Python或Mathematica代码会很方便。 - Yaroslav Bulatov
显示剩余5条评论
1个回答

4

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

  • 注意到中心是投影对的,因此要识别并仅保留在一组或另一组半球覆盖下的中心的一半。这些对是互补集。一个例子规则:所有包含顶点1的子集,以及在“赤道”上的那些,包含顶点2的子集,在该集合的“赤道”上,包含顶点3的子集,依此类推,保持边界半部分与最小索引顶点相邻。
  • 观察到对于每个子单形,要么子单形与顶点1相邻,要么距离简单形状为1。(原因:四面体中的每个新顶点都连接到四面体的每个先前顶点 - 因此每个子单形都与顶点1相关或者顶点1连接到简单形状中的每个顶点。)因此,每种类型的子单形(针对指定的顶点)只有两种情况。 (我们可以用决策来替换这个观察结果,只保留每个投影对中较小的成员,但是然后标记顶点的规则更加复杂。)
  • 四面体在顶点标签的置换下完全对称。因此,任何“有趣的部分”等同于另一部分,仅包含顶点的前导段 - 即可以在某个n的顶点范围[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}
    这些图形顶点没有其他权重可能。
    图形是K_{3}与0相交,以下图形符合图形选择规则:
    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},{},是您的正方形有趣集合。此标记没有零行列式。
    将其转换为代码留给读者作为练习(因为我得去上班了)。

有趣的观察,尽管我没有直接看到它们对应的算法。 - Yaroslav Bulatov
(1) 生成加权截面图并删除不允许的图。(2) 对于每个幸存的截面图,生成所有可行的四面体顶点标记,并删除体积为零的标记。在三维版本中,生成所有可能的加权图,然后说服自己除了上面的A和B之外的所有图形都是不允许或多余的,这个练习很有教育意义。对于标记,有两个部分--通过计算着陆在同一中心点的边缘重叠度来进行迭代,然后使用贪婪算法应用标签。 - Eric Towers
我发现使用新版本的群论函数有更直接的方法,但还是感谢你的努力。 - Yaroslav Bulatov

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接