Выдержка из книги
Препарата Ф.N.
Вычислительная геометрия Введение
Бентли и Шеймос [ Bentley, Shamos ( 1978) ] показали, что с небольшими изменениями в реализации этот алгоритм достигает линейной оценки сложности в среднем, и, по-видимому, имеется возможность его обобщения на случай пространств более высокой размерности. Для пользы дела коротко напомним идею алгоритма. Если число заданных точек N меньше некоторой константы Л / о, то оболочка вычисляется некоторым прямым методом. Если же N больше NQ, то процедура сначала произвольным образом разбивает множество из N точек на два под множества, содержащие примерно по N / 2 точек каждое. Результатом каждого из этих рекурсивных обращений к процедуре является выпуклый многоугольник. Оболочка исходного множества есть не что иное, как оболочка объединения оболочек подмножеств. Последняя может быть найдена за время, пропорциональное полному числу вершин обеих подоболочек. При разработке на основе этого метода алгоритма с линейной сложностью в среднем возникает проблема, связанная с шагом разбиения множества на части. Действительно, в том виде, как это сделано в разд.
![Бентли и Шеймос [ Bentley, Shamos ( 1978) ] показали, что с небольшими изменениями в реализации этот алгоритм достигает линейной оценки сложности в среднем, и, по-видимому, имеется возможность его обобщения на случай пространств более высокой размерности. Для пользы дела коротко напомним идею алгоритма. Если число заданных точек N меньше некоторой константы Л / о, то оболочка вычисляется некоторым прямым методом. Если же N больше NQ, то процедура сначала произвольным образом разбивает множество из N точек на два под множества, содержащие примерно по N / 2 точек каждое. Результатом каждого из этих рекурсивных обращений к процедуре является выпуклый многоугольник. Оболочка исходного множества есть не что иное, как оболочка объединения оболочек подмножеств. Последняя может быть найдена за время, пропорциональное полному числу вершин обеих подоболочек. При разработке на основе этого метода алгоритма с линейной сложностью в среднем возникает проблема, связанная с шагом разбиения множества на части. Действительно, в том виде, как это сделано в разд.](/pic/3302201rRBP3fL0004189931.png)