418
правок
Изменения
Новая страница: «{{notready}} Рассмотрим трёхмерный случай. <tex>n</tex>-мерный случай сводится к трёхмерному. == Алг...»
{{notready}}
Рассмотрим трёхмерный случай. <tex>n</tex>-мерный случай сводится к трёхмерному.
== Алгоритм ==
Выберем любые две точки <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>n</tex>-мерный случай сводится к трёхмерному.
== Алгоритм ==
Выберем любые две точки <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>.
