418
правок
Изменения
Нет описания правки
[[Файл:3dconvexhullconflictlist.png|200px|thumb|left]]
Перейдём к первому случаю. Пусть мы добавили точку <tex>p_r</tex> и рассматриваем грань <tex>f</tex>. <tex>e</tex> — ребро, принадлежащее horizon, <tex>f_1, f_2</tex> — грани, пересечение которых образовывало <tex>e</tex> в старой оболочке. Пусть <tex>p_t</tex> — ещё не добавленная точка, из которой видно <tex>f</tex>, тогда из неё видно и ребро <tex>e</tex>, причём как в новой, так и в старой выпуклой оболочке (так как новая включает в себя старую). Но это возможно, только если из <tex>p_t</tex> видно <tex>f_1</tex> или <tex>f_2</tex>. Значит, точки, с которыми у <tex>f</tex> есть конфликт — это только какие-то из точек, у которых есть конфликт у <tex>f_1</tex> и <tex>f_2</tex>.
==Время работы==
{{Лемма
|id=lemma1
|statement=
Пусть <tex>P</tex> — выпуклый многогранник с <tex>n</tex> вершинами. Тогда число его рёбер не превосходит <tex>3n - 6</tex>, а число его граней — <tex>2n - 4</tex>.
|proof=
[[Файл:3dconvexhullprojection.png|300px|thumb|right|Верхняя грань куба спроецировалась на внешнюю грань графа]]
«Спроецируем» многогранник на плоскость, как на картинке. Получили планарный граф, по формуле Эйлера имеем <tex>n - n_e + n_f = 2</tex>, где <tex>n_e</tex> — число рёбер, <tex>n_f</tex> — число граней. Каждая грань нашего графа имеет по меньшей мере 3 ребра, каждое ребро инцидентно двум граням, поэтому имеем <tex>2 n_e \geqslant 3 n_f</tex>. Тогда получаем <tex>n_f \leqslant 2n - 4</tex>, и, подставив это в формулу Эйлера, <tex>n_e \leqslant 3n - 6</tex>.
}}
