Список всех интересных сечений тетраэдра

Правильное решение для программирования в общих чертах:

• Заметьте, что центры входят в проективные пары, поэтому определите и сохраните только половину центров, которые находятся в той или иной полусферической оболочке набора центров. Пары дополняют друг друга. Пример правила: все подмножества, содержащие вершину 1, и те, что на «экваторе», те, которые содержат вершину 2, и на «экваторе» этого набора, те, которые содержат вершину 3, и т. д. рекурсивно сохраняя границу наполовину смежной с наименьшим индексом вершина.
• Заметим, что для каждого подсимплекса либо он смежн с вершиной 1, либо находится на расстоянии 1 от симплекса. (Причина: каждая новая вершина тетраэдра соединена с каждой предыдущей вершиной тетраэдра — следовательно, каждый подсимплекс либо инцидентен вершине 1, либо вершина 1 соединена с каждой вершиной симплекса.) Следовательно, существует только две совокупности каждого вид подсимплекса (относительно заданной вершины). (Мы можем заменить это наблюдение решением оставить только меньший член каждой проективной пары, но тогда правило маркировки вершин будет более сложным.)

• Тетраэдры полностью симметричны относительно перестановки меток вершин. Следовательно, любой «интересный участок» эквивалентен другому участку, содержащему только начальный сегмент вершин, т. е. может быть идентифицирован среди вершин Range[1,n] для некоторого n.

• Собрав вышеизложенное, мы обнаруживаем, что существует сюръекция из интересующего сечения на множество графов. Для каждого графа мы должны перечислить согласованные принадлежности вершин (описано позже). За исключением одной вершины, вершины графа идут парами

  • The pair contains all centers of a given cardinality (all subsimplices of a given dimension).
  • Один член пары содержит центры, инцидентные вершине 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}
Б: {0->2,2},{0->2,2},{2->2,1}

A имеет только одну маркировку: {1},{2},{} и представляет собой интересующий вас треугольный набор. Эта маркировка не имеет нулевого определителя.
B имеет только одну маркировку: {1,2},{1,3},{} и является интересующим вас квадратным множеством. Эта разметка не имеет нулевого определителя.

Преобразование в код оставлено читателю в качестве упражнения (потому что мне нужно уйти на работу).