Изменения
→Время работы
Выберем любые две точки <tex>p_1</tex> и <tex>p_2</tex>. Далее из оставшихся выберем точку <tex>p_3</tex>, которая не лежит на прямой, образованной точками <tex>p_1</tex> и <tex>p_2</tex>. После этого выберем точку <tex>p_4</tex>, которая не лежит на плоскости, образованной точками <tex>p_1, p_2</tex> и <tex>p_3</tex>. Если этого сделать не получилось, то запустим алгоритм для поиска выпуклой оболочки на плоскости.
Так мы получили тетраэдр <tex>p_1 p_2 p_3 p_4</tex>, который является выпуклой оболочкой этих четырёх точек. Сделаем random shuffle оставшихся точек <tex>p_5, ..., p_n</tex> и будем добавлять их по одной в выпуклую оболочку. Если <tex>p_i</tex> внутри или на границах выпуклой оболочки, то выпуклая оболочка не меняется на этом шаге. Иначе из имеющейся выпуклой оболочки надо удалить все видимые из данной точки грани и добавить новые — из точки до каждого ребра, образующего horizon (см. картинки; на них белые грани видны из точки <tex>p_r</tex>). После этого нужно смержить соседние грани, которые получились копланарнымикомпланарными.
[[Файл:3dconvexhullhorizon.png]] [[Файл:3dconvexhulladd.png]]
Для выяснения, какие грани видны из точки, будем хранить двудольный граф <tex>G</tex>, называемый conflict graph, в одной доле которого будут точки, которые ещё не добавлены в выпуклую оболочку, а в другой — имеющиеся на данный момент грани выпуклой оболочки. Ребро между точкой <tex>p</tex> и гранью <tex>f</tex> в этом графе означает, что из <tex>p</tex> видна <tex>f</tex>, то есть они находятся в конфликте (in conflict): они не могут сосуществовать в выпуклой оболочке.
Инициализация графа для тетраэдра тривиальна: для каждой точки определяем, какие грани видны из неё. Далее на каждом шаге после добавления точки <tex>p_r</tex> удалим из графа соответствующие удаляемым из выпуклой оболочки граням вершины и инцидентные им рёбра: просто удаляем все достижимые из <tex>p_r</tex> вершины. Также удалим вершину, соответствующую <tex>p_r</tex>. Далее добавляем новые грани выпуклой оболочки. Необходимо найти их конфликты. Сами грани представляют из себя треугольники, если, конечно, они не были смержены с уже имеющимися гранями. Во втором случае новая грань находится в конфликте с теми же точками, что и старая грань, т.к. смерженные грани копланарныкомпланарны.
[[Файл:3dconvexhullconflictlist.png|200px|thumb|left]]
|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>(если не удаётся это понять, можно представить двудольный граф, где слева грани, а справа рёбра. Из каждого ребра исходит ровно 2 вершины, а в каждую грань входит хотя бы 3). Тогда получаем <tex>n_f \leqslant 2n - 4</tex>, и, подставив это в формулу Эйлера, <tex>n_e \leqslant 3n - 6</tex>.
}}
Шаги перед добавлением точек можно сделать за <tex>O(n \log n)</tex>. Очередной шаг требует константного времени, если <tex>m_r</tex> — число конфликтных граней для добавляемой точки — равно нулю (то есть когда точка внутри или на границах имеющейся выпуклой оболочки). Иначе этот шаг требует <tex>O(m_r)</tex> времени плюс время на удаление видимых рёбер (удалить ребро можно не больше одного раза, поэтому можно считать, что этот шаг лишь изменит константу во времени создания новых рёбер) и изменение графа конфликтов.
Заметим, что <tex>m_r</tex> — число граней, удалённых на очередном шаге алгоритма, поэтому по [[#lemma2|лемме 2]] <tex>E(\sum_{r = 5}^{n} m_r ) = O(n)</tex>.
При изменении графа конфликтов на шаге <tex>r</tex> требуется время, равное сумме числа конфликтных точек для смежных граней каждого ребра на horizon. Это меньше либо равно числу всех конфликтных точек для всех граней. Утверждается, что оно равно <tex>O(n \log n)</tex>, и это надо как-то доказать (в де Берге есть, надо разобраться и дополнить), и тогда теорема доказана.
}}
