Алгоритмы вычислительной геометрии. Выпуклые оболочки: связь с задачей сортировки и оптимальные алгоритмы.

Abstract

В продолжение статьи предыдущего номера рассматриваются алгоритмы построения выпуклой оболочки на плоскости. Связь этой задачи с задачей сортировки позволяет найти нижнюю оценку сложности задачи построения выпуклой оболочки. Кроме того, аналогия между этими двумя задачами приводит к некоторым оптимальным по сложности алгоритмам построения выпуклой оболочки. Рассматриваются также алгоритмы Киркпатрика-Зайделя и Чена, асимптотическая сложность которых зависит от размера построенной выпуклой оболочки. (С. 6-18)