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

Материал из Викиконспекты
Версия от 16:46, 16 января 2014; Katyatitkova (обсуждение | вклад) (Новая страница: «{{notready}} Рассмотрим трёхмерный случай. <tex>n</tex>-мерный случай сводится к трёхмерному. == Алг...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Конспект не готов.

Рассмотрим трёхмерный случай. [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].