Listing toutes les sections intéressantes d'un tétraèdre

Question

mise à jour de réponse, 12/22: En utilisant Peter Shor de observation qu'il ya un morphisme entre les sections distinctes et permutations des objets sur le cube, la liste de toutes ces permutations en représentant un groupe de symétries cube comme un sous-groupe de SymmetricGroup [8] et en utilisant GroupElements/Permute, trouver des missions barycentre utilisant le solveur de Mathematica, ensembles de sélection de point avec des valeurs singulières distinctes, quelques détails et code complet donné here

question

Une section 2D intéressante est un plan qui passe par le centre d'une 3D régulière simplex et 2 autres points dont chacun est un centroïde d'un sous-ensemble non-vide de sommets. Il est défini par deux sous-ensembles de sommets. Par exemple {{1}, {1,2}} donne un plan défini par 3 points - centre du tétraèdre, premier sommet, et moyenne des premier et second sommets.

un ensemble intéressant de sections est un ensemble dans lequel pas deux sections définissent le même plan sous le sommet réétiquetage. Par exemple, définir {{{1}, {2}}, {{3}, {4}}} n'est pas intéressant. Existe-t-il une approche efficace pour trouver un ensemble intéressant de sections intéressantes? J'ai besoin de quelque chose qui pourrait généraliser à un problème analogue pour les sections 3D de 7D simplex, et finir du jour au lendemain.

Mon approche est tentée ci-dessous. Un problème est que si vous ignorez la géométrie, certaines sections équivalentes vont être conservées, donc j'obtiens 10 sections au lieu de 3. Un plus gros problème est que j'ai utilisé la force brute et que ça n'a certainement pas d'échelle et (nécessite 10^17 comparaisons pour simplex 7D)

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

Voici le code Mathematica pour générer l'image ci-dessus.

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

La solution de programmation correcte est, dans les grandes lignes:

• observer que les centres viennent en paires projectives - afin d'identifier et de ne conserver que la moitié des centres qui se trouvent dans une ou les autres couvertures hémisphériques de l'ensemble des centres. Les paires sont des compléments les uns des autres. Un exemple de règle: tous les sous-ensembles contenant le sommet 1, et ceux sur l'équateur, ceux contenant le sommet 2, et sur l'équateur, ceux contenant le sommet 3, et ainsi de suite récursivement garder la moitié adjacente au plus petit indexé sommet.
• Observer que pour chaque subsimplex, soit le subsimplex est adjacent au sommet 1 ou il est une distance loin de simplex. (Cause: chaque nouveau sommet du tétraèdre est attaché à chaque sommet précédent du tétraèdre - par conséquent, chaque sous-ensemble est soit incident sur le sommet 1, soit le sommet 1 est connecté à chaque sommet du simplexe.) Il n'y a donc que deux populations sorte de subsimplex (par rapport à un sommet spécifié). (Nous pouvons remplacer cette observation par la décision de ne garder que le plus petit membre de chaque paire projective, mais la règle d'étiquetage des sommets est plus compliquée.)

• Les tétraèdres sont complètement symétriques par permutation des marqueurs de sommet. Par conséquent, toute "section intéressante" est équivalente à une autre section ne contenant que le segment principal de sommets, c'est-à-dire qu'elle peut être identifiée parmi les sommets Range [1, n] pour un certain n.

• collecte qui précède, nous constatons qu'il ya une surjection de section intéressante à un ensemble de graphiques. Pour chaque graphe, nous devons énumérer les appartenances au sommet cohérentes (décrites plus loin).À l'exception d'un sommet, les sommets du graphique viennent par paires

  • La paire contient tous les centres d'une cardinalité donnée (tous les sous-impléments d'une dimension donnée).
  • Un membre de la paire contient des centres incident sur le sommet 1.
  • L'autre élément de la paire contient des centres pas incident sur le sommet 1.
  • Le sommet spécial est soit le centre contenant tous les sommets ou sa paire projective (le "centre vide").
  • Si un graphe contient un membre d'une paire, il doit contenir (au moins) les centres contenant des éléments incidents sur 1 (ou les vertices peuvent être ré-étiquetés pour que cela soit ainsi).
• Les bords du graphique sont pondérés. Le poids est le nombre de sommets partagés par les deux centres. Il existe des restrictions sur le poids basées sur la cardinalité des centres à chaque extrémité et selon que les deux sommets sont tous les deux premiers membres, les deux seconds membres ou sont l'un de chaque. ("Un de chaque" ne peut pas partager le sommet 1, par exemple.)
• Un graphe est un sous-graphe complet sur l'ensemble des sommets, contenant le sommet spécial. Par exemple pour le tétraèdre, un graphe est un K_ {3} sur l'ensemble des sommets identifiés ci-dessus, avec un sommet spécial et avec des poids de bord.
• Une section est un graphe avec une application cohérente d'étiquettes aux centres à la fin de chaque arête (ie marqué de façon cohérente pour respecter le nombre de sommets partagés indiqué par le poids du bord et chaque sous-ensemble sommet 1). Un graphe donné peut donc représenter plusieurs sections (via différentes étiquettes). (Il n'y a pas autant d'options que de sens en une seconde.)
• Une section n'est pas intéressante si la matrice faite à partir des coordonnées de ses centres a un déterminant nul.

Dans le cas de trois dimensions, avec quatre sommets, nous obtenons les ensembles suivants (nous utilisons la courte paire projective parce qu'il ya suffisamment de visibilité dans cet exemple pour ne pas nécessiter la règle de rejet de l'étiquetage des sommets plus simple):
0 : paire projective de {1,2,3,4}
1: {1}
1 ': {2}, {3}, {4}
2: {1,2}, {1,3 }, {1,4}
2 ': paires projectives à 2 (ainsi omis)
3: paires projectives à 1' (ainsi omis)
3 ': projective pai rs à 1 (donc omis)

contraintes d'étiquetage:
{0-> x, x} {
0-> x », x} {
1-> 1,1} -: centres non admissibles ne sont pas inclus deux fois
{1> 1' , 0} {1
> 2,1}
{2-> 2,1}
Aucun autre poids sont possibles avec ces sommets du graphe.

Un graphique est un événement K_ {3} sur 0, les graphiques suivants les règles de survivre sélection graphique:
A: {0-> 1,1}, {0-> 1' , 1}, {1 -> 1 ', 0}
B: {0-> 2,2}, {0-> 2,2}, {2-> 2,1}

A ne possède qu'un seul libellé: {1} , {2}, {} et est votre ensemble triangulaire intéressant.Cet étiquetage n'a pas de déterminant nul.
B n'a qu'un seul libellé: {1,2}, {1,3}, {} et votre carré est intéressant. Cet étiquetage n'a pas de déterminant nul.

La conversion en code est laissée au lecteur comme exercice (parce que je dois partir pour le travail).