Алгоритмы вычислительной геометрии. Выпуклые оболочки: связь с задачей сортировки и оптимальные алгоритмы
Ивановский С.А., Преображенский А.С., Симончик С.К.
В продолжение статьи предыдущего номера рассматриваются алгоритмы построения выпуклой оболочки на плоскости. Связь этой задачи с задачей сортировки позволяет найти нижнюю оценку сложности задачи построения выпуклой оболочки. Кроме того, аналогия между этими двумя задачами приводит к некоторым оптимальным по сложности алгоритмам построения выпуклой оболочки. Рассматриваются также алгоритмы Киркпатрика-Зайделя и Чена, асимптотическая сложность которых зависит от размера
Categorías:
Año:
2007
Idioma:
russian
Páginas:
13
Archivo:
PDF, 997 KB
IPFS:
,
russian, 2007