Выпуклая оболочка в 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].