Pavlovsky я вас правильно понял?
На всякий случай объясню подробнее. Пусть в нашем алгоритме критической операцией будет добавление к решению из k-1 точек точки
![$p_k$ $p_k$](https://dxdy-03.korotkov.co.uk/f/a/2/8/a28020cb9b58a3a875adec3adf5d824a82.png)
. Естественно необходимо проверить можно ли добавить очередную точку к решению. Это можно сделать двумя способами.
1) Перебрать все тройки точек из решения из k-1 точек и проверить принадлежит ли точка
![$p_k$ $p_k$](https://dxdy-03.korotkov.co.uk/f/a/2/8/a28020cb9b58a3a875adec3adf5d824a82.png)
этой плоскости.
2)Перенесем проверку на шаг итерации раньше. Будем вести список допустимых точек. Которые можно добавлять к текущему решению без всяких проверок. После добавления в решение точки
![$p_{k-1}$ $p_{k-1}$](https://dxdy-03.korotkov.co.uk/f/a/9/0/a90c7569d63e5a165e14749e67ea791c82.png)
удалим из списка допустимых точек все точки лежащие в плоскостях образуемых двумя точками из ращения из k-2 точек и точки
![$p_{k-1}$ $p_{k-1}$](https://dxdy-03.korotkov.co.uk/f/a/9/0/a90c7569d63e5a165e14749e67ea791c82.png)
.
Очевидно второй вариант заметно быстрее.
-- Вс мар 13, 2016 20:20:46 --it is not easy to figure this out in general for arbitrary three points.
Значит надо искать частные случаи. Например:
В каждой плоскости
![$1 \times n \times n$ $1 \times n \times n$](https://dxdy-04.korotkov.co.uk/f/7/a/5/7a5a3f17d841b6846a6ddd41d8fa478c82.png)
может быть не более трех точек
Когда в слои
![$1 \times n \times n$ $1 \times n \times n$](https://dxdy-04.korotkov.co.uk/f/7/a/5/7a5a3f17d841b6846a6ddd41d8fa478c82.png)
;
![$n \times 1 \times n$ $n \times 1 \times n$](https://dxdy-04.korotkov.co.uk/f/7/a/d/7ad43d3a3bfcb81c775061add1056c5a82.png)
;
![$n \times n \times 1$ $n \times n \times 1$](https://dxdy-01.korotkov.co.uk/f/c/7/0/c70facef4c89afb5c86b7775f39a52d982.png)
добавляется третья точка. Все остальные точки слоя должны быть удалены из списка допустимых точек.
-- Вс мар 13, 2016 20:23:13 --Есть и более изощренные частные случаи, но это пока военная тайна.
![Very Happy :D](./images/smilies/icon_biggrin.gif)