Геометрические фантазии

[juna]

Зададимся вопросом: на какое минимальное количество треугольных пирамид (симплексов) может быть разбит заданный многогранник. Например, факты таковы: для куба - 5, для икосаэдра - 16, для додекаэдра - 26. Возможна ли аналитическая формула? Мне лишь удалось доказать, что искомое число должно быть больше либо равно количеству вершин многогранника минус три.

[Кролик]

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

Если же существует труднорешаемая задача, сводящаяся к Вашей, то думаю, следует отбросить мечты про аналитические формулы.

[незваный гость]

А октаэдр? У меня меньше 4 не получается. А у Вас?

[maxal]

Вот наткнулся на статью: DECOMPOSITION OF CONVEX POLYTOPES INTO SIMPLICES.

[Руст]

Оценка снизу правильная и неулучшаемя. Достаточно построить пирамиду на n-1 многоугольнике. Другое дело существует фигуры (типа октаэдра), для которых эта оценка не является точной. Можно получить и квадратичную оценку сверху.

[juna]

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

Любое конструирование многогранника начинается с прикладывания одной пирамиды к другой (связывания их по одной грани) и т.д. Поэтому все вершины исходного многогранника получаются из вершин прикладываемых пирамид. Пусть у многогранника В вершин.
Тогда В=4K-S, где S=3a+4b. Число K – это число пирамид разбиения, S – число вершин, которые не нужно учитывать. Число S складывается из a прикладываний пирамиды по одной грани (не нужно учитывать 3 вершины, добавляется только одна), b прикладываний по 2-м или 3-м граням (не прибавляется ни одной новой вершины). Кроме этого суммарное число прикладываний на единицу меньше числа пирамид разбиения: a+b=K-1. Комбинируя эти три формулы, получаем a=B-4, K=B-3+b. Поскольку b>=0, то K>=B-3 ч.т.д.
Заметим, что число прикладываний по одной грани строго определено a=B-4, для многогранников типа октаэдра четыре пирамиды требуется именно потому, что осуществляется одно прикладывание по двум граням. Итак, если удается получить строгое выражение для числа прикладываний по двум, трем граням, то можно мечтать об аналитической формуле. Но, увы – пока не удается. Вообще эта тема хороша для обобщений на многомерные пространства, но об этом в следующий раз.

[maxal]

Артамонов Ю.Н. писал(а):

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

В указанной выше статье как раз и рассматривается общий многомерный случай и даны нижние и верхние оценки на число симплексов.

[juna]

Не хочется закрывать интересную тему, поэтому продолжим…
Утверждается, что объем правильного симплекса со стороной длины $a$ в $M$-мерном пространстве выражается как $V_M=\frac {a^M}{M!}\frac {\sqrt {M+1}}{{(\sqrt{2})}^M}$. Понятие объем в многомерном пространстве развивается по аналогии из одномерного, двухмерного, трехмерного случая.
Требуется проверить истинность утверждения.

[незваный гость]

Руст писал(а):

Оценка снизу правильная и неулучшаемя. Достаточно построить пирамиду на n-1 многоугольнике. Другое дело существует фигуры (типа октаэдра), для которых эта оценка не является точной. Можно получить и квадратичную оценку сверху.

У меня получилась линейная оценка сверху $2 V - 4$ для выпуклого многограника.

Примерно так -- берем точку внутри, разбиваем на пирамиды (с вершиной в выбранной точке). Для каждой пирамиды достаточно $n-2$ симплексов ($n$ -- количество сторон у грани). Суммируем, получаем $\sum\limits_f n_f - 2F$. Первое слагаемое равно удвоенному числу ребер, поскольку каждое ребро принадлежит ровно двум граням. Имеем $2 E - 2F = 2 V - 4$.

Оценку, разумеется, можно улучшить, как же без этого. Одна из идей (сразу) -- брать не точку внутри, а одну из вершин.

[juna]

Оценку эту, как Вы и сами указали, можно улучшать, несмотря на ее линейность. Можно показать, что разбиение многогранника на минимальное количество симплексов исключает прикладывания по трем граням в принципе (а у Вас, по крайней мере, последнее прикладывание осуществляется по трем граням). Постараюсь этот тезис доказать а заодно и прояснить ситуацию.
Введем характеристику многогранника: ${\beta}_{ij}$ - количество i-мерных пространств в j-мерном. Например, ${\beta}_{12}$ - количество ребер в грани и т.д. Данные характеристики обладают очевидными свойствами:
${\beta}_{03}-{\beta}_{13}+{\beta}_{23}=2$ (известное соотношение);
${\beta}_{01}={\beta}_{21}=2$;
${\beta}_{02}={\beta}_{12}={\beta}_{22}$; ${\beta}_{10}={\beta}_{20}$;
${\beta}_{ii}={\beta}_{(i-1)i}({\beta}_{i(i-1)}-1)$.
Предположим, что конструировать многогранник мы можем тремя способами: прикладывания по одной грани, по двум, по трем. По четырем в трехмерном пространстве нет смысла рассматривать. Пусть ${{\beta}_{03}}^*$, ${{\beta}_{13}}^*$, ${{\beta}_{23}}^*$ - количество вершин, ребер, граней на каком-то этапе конструирования соответственно. Тогда на следующем шаге мы можем выбрать любой из трех указанных способов. При этом указанные характеристики меняются.
Прикладывания по одной грани: ${{\beta}_{03}}={{\beta}_{03}}^*+1$; ${{\beta}_{13}}={{\beta}_{13}}^*+3$; ${{\beta}_{23}}={{\beta}_{23}}^*+2$.
Прикладывания по двум граням: ${{\beta}_{03}}=${{\beta}_{03}}^*$; ${{\beta}_{13}}={{\beta}_{13}}^*$; ${{\beta}_{23}}={{\beta}_{23}}^*$.
Прикладывания по трем граням: ${{\beta}_{03}}=${{\beta}_{03}}^*$; ${{\beta}_{13}}={{\beta}_{13}}^*-3$; ${{\beta}_{23}}={{\beta}_{23}}^*-2$.
Количество прикладываний по одной грани строго определено. Поэтому, можно начинать конструирование после всех прикладываний по одной грани, тогда указанные бета-характеристики будут следующие: ${{\beta}_{03}}^*=4+({{\beta}_{03}}-4)={{\beta}_{03}}$; ${{\beta}_{13}}^*=6+3({{\beta}_{03}}-4)-\sum\limits_{i=1}^{{\beta}_{23}}{({\beta}_{12}-3)}=3{{\beta}_{03}}-6-\sum\limits_{i=1}^{{\beta}_{23}}{({\beta}_{12}-3)}$, характеристику ${{\beta}_{23}}$ нет смысла выражать, т.к. она однозначно зависит от первых двух, характеристика $ {\beta}_{03}$ - количество вершин исходного многогранника. Заметим, что прикладывания по двум граням не оказывает никакого влияния на бета-характеристики – и не могут быть обнаружены при таком подходе. Прикладывание по трем граням уменьшает количество ребер, поэтому, если обозначить через $\eta$ – количество прикладываний по трем граням, то количество ребер искомого многогранника выразится:
${\beta}_{13}=3{{\beta}_{03}}-6-{\sum\limits_{i=1}^{{\beta}_{23}}{({\beta}_{12}-3)}}-3{\eta}$
$\eta=\frac{{3{\beta}_{03}}-6-\sum\limits_{i=1}^{{\beta}_{23}}{({\beta}_{12}-3)}- {\beta}_{13}}{3}$. Пусть $\chi$ - искомое минимальное количество симплексов, тогда ${\chi}\geqslant {2{\beta}_{03}-5+{\beta}_{23}-\frac{\sum\limits_{i=1}^{{\beta}_{23}}{{\beta}_{12}}}{3}-\frac {{\beta}_{13}}{3}$
Далее можно доказать, что
${2{\beta}_{03}-5+{\beta}_{23}-\frac{\sum\limits_{i=1}^{{\beta}_{23}}{{\beta}_{12}}}{3}-\frac {{\beta}_{13}}{3}={\beta}_{03}-3$ Т.е. нет здесь никаких прикладываний по трем граням (нижнее ограничение неулучшаемо). Прикладывания по двум граням нельзя никак зафиксировать – конструктивно они ничего не меняют, меняют лишь метрически. Поэтому получить аналитическую формулу при таком подходе невозможно.

[незваный гость]

Я не понял, что Вы хотите сказать. $V - 3$ -- хорошая оценка снизу (То есть, для любого многогранника необходимо по крайней мере $V - 3$ симплексов). Я указал оценку сверху $2V-4$, готов ее улучшить до $2 V - 7$ (То есть, для любого многогранника достаточно не более чем $2V - 7$ симплексов). Обе оценки неулучшаемы в том смысле, что существуют многогранники на которых они выполняются. Если исключить симплекс, то оценку сверху можно улучшить до $2 V - 8$. Но оценки снизу и сверху -- просто разные.

[juna]

То, что оценки верхняя и нижняя – разные – я понял.
Ставилась задача показать, что оценка снизу не улучшаема ни для какого из многогранников – искомая оценка складывается из количества прикладываний по одной грани, которое жестко зафиксировано числом B-4, и количества прикладываний по двум, трем граням. Если нижнюю оценку можно улучшить – то только за счет прикладываний по трем граням, т.к. количество прикладываний по двум граням вообще не поддается аналитическому расчету. Я выразил количество прикладываний по трем граням и получил, что оно равно нулю. Значит, В-3 – нижняя граница неулучшаема. Что же касается вашей верхней оценки 2В-4, то в рассуждении использовалось прикладывание по трем граням – значит оно обречено на улучшение.

[незваный гость]

$2V - 7$ реализуется для тетраэдра, $2V - 8$ -- для октаэдра. А вот что такое прикладывание -- не знаю.

У Вас есть лучшие верхние или нижние оценки -- поделитесь. Я всего лишь улучшил высказанную Рустом, и поделился. Подозреваю, что указанная maxal'ом статья содержит более точные и более глубокие результаты. Мой -- на поверхности, и статьи не заслуживает. Именно простота и толкнула меня написать...

[juna]

Грань одного симплекса прикладываем к грани другого - вот и считаем такие прикладывания и проводим их классификацию. Лучшей нижней оценки нет. Если в верхней оценке, кроме вершин использовать и ребра или другие бета-характеристики (см. предыдущее), то видимо ее можно улучшить - сделать более гибкой. Ваши рассуждения по поводу 2V-4 - лежат на поверхности - просты, эффектны. В статье, на которую указал maxal, рассматривается многомерный случай, но верхней оценки я там не нашел (может чего не понял).