Асимптотика многомерного многогранника

[B@R5uk]

Меня тут вдруг заинтересовала такая задача. Предположим, у нас имеется N-мерное пространство и M полупространств в нём ($M>N$) ограничивают некий выпуклый многомерный многогранник. В связи с этим возникают такие вопросы:
1) асимптотически как много вершин у такого многогранника?
2) асимптотически как много рёбер в среднем сходится в одной вершине?
3) если где-нибудь через середину многогранника провести сечение ещё одним полупространством, то ассимптотически как много вершин на нём окажется?
4) число гиперграней, очевидно, не может превышать M.

Для $N=1$ всё элементарно просто: любой "многогранник" в одномерном пространстве — это отрезок. Поэтому ответами на вопросы 1, 2 и 3 будут конкретные числа 2, 1 и 1, которые даже не зависят от числа ограничивающих отрезок "полупространств" (лучей), так как все, кроме двух, окажутся неактуальными. Неинтересный случай.

Случай $N=2$ всё ещё прост, но уже интересней. "Многогранник" является многоугольником, число его вершин и "гиперграней" совпадает и равно M. В каждой вершине сходится две грани, а любое сечение не может иметь больше двух вершин (надо заметить, как и в предыдущем случае, это число совпадает с размерностью). Ответы на вопросы 1, 2 и 3 — это числа M, 2 и 2.

При переходе к $N=3$ происходит качественный скачок. В одной вершине может сходится много (вообще говоря, сколько угодно) граней. Интуиция подсказывает мне (возможно неверно), что число вершин в многограннике будет максимально (при фиксированном числе граней), когда в вершинах сходится в среднем одинаковое число граней.

Чтобы построить асимптотику, я бы для затравки взял тетраэдр (количество вершин-граней равно 4-4) и отсёк бы каждую вершину плоскостью на расстоянии трети ребра. Получится фигура с $4+4=8$ гранями, и $4\times 3=12$ вершинами. Здесь 3 — это количество рёбер, сходящихся в одной вершине. Эта величина не изменяется при такой операции усечения (поскольку, как мы видели для $N=2$ сечение содержит всего две вершины — на одну меньше). Поэтому, при повторении операции получим фигуру с $8+12=20$ гранями и $12\times 3=36$ вершинами. На следующей итерации будет $20+36=56$ и $36\times 3=108$. Число граней $F_k$ и число вершин $V_k$ зависят от номера итерации k следующим образом:

$$V_k=4\cdot 3^{k}$$

$$F_k=4+\sum\limits_{l=1}^{k-1}{V_l}=4+4\cdot\sum\limits_{l=1}^{k-1}{3^l}=2\cdot\left(3^k+1\right)$$

Видно, что число вершин приблизительно в два раза больше числа граней M. Теорема Эйлера так же сообщит нам, что число рёбер будет в три раза больше числа граней M.

Таким образом, для $N=3$ получаются некоторые ответы на вопросы 1 и 2 (в предположении, что моя интуиция верна) — это величины $0.5\cdot M$ и 3 (второе число всё ещё совпадает с размерностью). Надо заметить, что тело, которое получается при описанной выше процедуре, имеет весьма сомнительную фрактальную природу. У него 4 больших грани, которые по мере итерирования стремятся к кругу. Затем у него 4 грани по-меньше, которые так же по мере итерирования стремятся к кругу, затем у него ещё 12 ещё меньших граней, которые так же по мере итерирования стремятся к кругу. И так далее: 36 кругов по-мельче, 108 кругов ещё мельче... Возможно, что если строить тело равномерно накидав точки на сферу и взяв выпуклую оболочку, мы получим совсем другие пропорции между гранями, рёбрами и вершинами.

С третьим вопросом возникают ещё более серьёзные проблемы. Может случиться так, что выпуклый многогранник — это пирамида и полупространство отсекает как раз её вершину. Тогда вершин в сечении будет $M-1$. А может быть так, что отсекается вершина, в которой сходится три ребра. Тогда вершин в сечении будет всего три. Это крайние и не очень интересные случаи. Хотелось бы знать, что происходит "в среднем". Например, сечение тетраэдра ($M=4$) может быть четырёхугольником, сечение куба ($M=6$) может быть шестиугольником, сечение октаэдра ($M=8$) и додекаэдра ($M=12$) — тоже шестиугольником, а икосаэдра ($M=20$) — десятиугольником. При росте M будет ли это "среднее" число вершин сечения расти пропорционально? Или же как корень из M? Как логарифм? Или же как-то по-другому?

Что творится в размерностях выше, боюсь даже начать себе представлять. Например, я недавно узнал, что при переходе к $N=4$ жёсткие конструкции получаются, когда гиперграни стыкуются не в вершинах (как это было при $N=3$), а в рёбрах! Можно ли это назвать качественным скачком? Какие ответы ожидать на мои исходные вопросы? Я даже не знаю с какой стороны подступиться.

[Утундрий]

Тут, на мой взгляд, остро не хватает уточнения особенностей рассечения. Ибо, ежели сечь абы как, то и получится абы что (включая пустое множество). Абер другое дело, когда преследуется некая цель. Чтобы вершин было побольше или ещё что-то в таком духе.

[arseniiv]

Утундрий в сообщении #1498907 писал(а):

Ибо, ежели сечь абы как, то и получится абы что (включая пустое множество).

Можно было бы например взять независимые стандартно многомерно-нормально распределённые векторы $\mathbf a_i$ и сопоставить им полупространства $\{\mathbf r \mid (\mathbf r, \mathbf a_i) \leqslant (\mathbf a_i, \mathbf a_i)\}$. Но не знаю, насколько такое распределение соответствует интуитивному образу B@R5uk; например соответствует ли моему, не могу понять.

Если выбирать какие-то другие похожие распределения, можно задавать распределение $|\mathbf a_i|$ (а $\operatorname{sgn} \mathbf a_i := \mathbf a_i / |\mathbf a_i|$ должен быть распределён равномерно по $N - 1$-мерной сфере всегда, если только мы не хотим чего-то совсем хитрого, но скорее всего мы тогда не будем принимать и независимость разных $\mathbf a_i$).

(P. S. Тема интересная, но могу только подписаться на неё.)

[B@R5uk]

Утундрий в сообщении #1498907 писал(а):

Абер другое дело, когда преследуется некая цель. Чтобы вершин было побольше или ещё что-то в таком духе.

Да. Вершин по-больше. То есть в первом вопросе подразумевается, что размерность пространства и количество гиперграней фиксировано, и спрашивается, "как велико может быть при таких условиях число вершин?" Во втором и третьем вопросе рассматриваются как раз такие максимальные многогранники (и близкие к ним по числу вершин), и в третьем сечение строится таким образом, чтобы количество вершин в нём тоже было максимально. Это, вообще говоря, два противоречащих друг другу требования (контрпример в 3D: пирамида), но первое из них в приоритете.

Я тут поразмышлял над пространствами высшей размерности и вспомнил такие факты. В них всегда существуют аналоги куба/квадрата и тетраэдра/треугольника.

Первый строится явно как все возможные комбинации знаков плюс-минус у радиус-вектора, координаты которого по модулю равны единице. Такое гипертело имеет $2^N$ вершин и ограничивается $M=2N$ полупространствами (по два на каждое измерение). Его рёбра имеют длину 2, а центр лежит в начале координат. Из каждой вершины выходит по N рёбер, по одному в каждую вершину, отличающуюся от исходной знаком только в одной координате.

Второе тело можно построить по индукции, беря вершины в координатах, полученных для размерности $N-1$ и добавляя ещё одну, равноудалённую от всех предыдущих на фиксированное расстояние, одинаковое для всех размерностей. Эту вершину всегда можно выбрать двумя способами (поскольку гиперплоскость делит пространство на две части), можно взять любую. Выпуклая оболочка этих вершин и будет искомым гипертелом. У него будет $N+1$ вершина и $M=N+1$ гипергрань (эти величины равны, поскольку есть пары: вершина — противоположная её гипергрань). Из каждой вершины будет выходить по N рёбер. И, видимо, это минимально возможное число рёбер, инцидентных любой вершине N-мерного многогранника. Не знаю, как это строго доказать, просто интуиция.

Из первого примера можно сделать заключение, что при ответе на первый вопрос в общем случае в асимптотике должна быть степень.

-- 04.01.2021, 14:54 --

arseniiv в сообщении #1498916 писал(а):

Можно было бы например взять независимые стандартно многомерно-нормально распределённые векторы $\mathbf a_i$ и сопоставить им полупространства $\{\mathbf r \mid (\mathbf r, \mathbf a_i) \leqslant (\mathbf a_i, \mathbf a_i)\}$.

Это тоже хороший вариант для численного моделирования вопроса, если уметь рационально строить вершины по ограничивающим плоскостям. Наивный подход с перебором всех возможных комбинаций гиперплоскостей для выделения вершин даст экспоненциальную сложность. В то же время, если накидать на N-мерную сферу точек, то есть достаточно эффективные алгоритмы построения выпуклой оболочки в пространстве любой размерности.

[B@R5uk]

Максимальное число возможных вершин многогранника можно сверху очень грубо оценить числом возможных вершин, образующихся на пересечении заданного числа полупространств. А именно, если в пространстве размерности N имеется M ограничивающих полупространств, то, чтобы задать какую-то вершину, надо выбрать N таких полупространств. Выбор можно сделать $C_M^N$ способами. Но из всего этого созвездия точек лишь малая горстка в центре будет вершинами многогранника.

Например, в трёхмерном пространстве у додекаэдра 12 граней, значит потенциальное число точек, где эти грани будут пересекаться равно $C_{12}^3=220$. При этом реальное число вершин у него 20. С икосаэдром ещё интересней: $C_{20}^3=1140$ против 12, но даже из этих потенциальных 1140 не все существуют, так как в икосаэдра есть параллельные грани.

Апофеозом параллельности является N-мерный куб. У него $M=2N$ гиперграней, что, по идее, должно дать $C_{2N}^N\simeq 4^N\exp(-\theta/(8N))/\sqrt{\pi N}$ гиперграней, но из них в принципе осуществимо из-за параллельности и действительно присутствует в многограннике только $2^N$.

[Sender]

B@R5uk в сообщении #1498826 писал(а):

Надо заметить, что тело, которое получается при описанной выше процедуре, имеет весьма сомнительную фрактальную природу.

Если хочется чего-то поравномернее, можно вспомнить тему с фуллеренами(в ней есть ссылки и на более ранние обсуждения).
https://dxdy.ru/topic62800.html