Выпуклая оболочка в n-мерном пространстве

Конспект написан не до конца, но основные вещи уже есть.

Рассмотрим трёхмерный случай. [math]n[/math]-мерный сводится к трёхмерному.

Суть алгоритма

Выберем любые две точки [math]p_1[/math] и [math]p_2[/math]. Далее из оставшихся выберем точку [math]p_3[/math], которая не лежит на прямой, образованной точками [math]p_1[/math] и [math]p_2[/math]. После этого выберем точку [math]p_4[/math], которая не лежит на плоскости, образованной точками [math]p_1, p_2[/math] и [math]p_3[/math]. Если этого сделать не получилось, то запустим алгоритм для поиска выпуклой оболочки на плоскости.

Так мы получили тетраэдр [math]p_1 p_2 p_3 p_4[/math], который является выпуклой оболочкой этих четырёх точек. Сделаем random shuffle оставшихся точек [math]p_5, ..., p_n[/math] и будем добавлять их по одной в выпуклую оболочку. Если [math]p_i[/math] внутри или на границах выпуклой оболочки, то выпуклая оболочка не меняется на этом шаге. Иначе из имеющейся выпуклой оболочки надо удалить все видимые из данной точки грани и добавить новые — из точки до каждого ребра, образующего horizon (см. картинки). После этого нужно смержить соседние грани, которые получились копланарными.