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

  • С.К. Симончик
  • А.С. Преображенский
  • С.А. Ивановский

Аннотация

В продолжение статьи предыдущего номера рассматриваются алгоритмы построения выпуклой оболочки на плоскости. Связь этой задачи с задачей сортировки позволяет найти нижнюю оценку сложности задачи построения выпуклой оболочки. Кроме того, аналогия между этими двумя задачами приводит к некоторым оптимальным по сложности алгоритмам построения выпуклой оболочки. Рассматриваются также алгоритмы Киркпатрика-Зайделя и Чена, асимптотическая сложность которых зависит от размера построенной выпуклой оболочки. (С. 6-18)
Опубликован
2014-01-17
Как цитировать
Симончик, С., Преображенский, А., & Ивановский, С. (2014). Алгоритмы вычислительной геометрии. Выпуклые оболочки: связь с задачей сортировки и оптимальные алгоритмы. Компьютерные инструменты в образовании, (2). извлечено от http://cte.eltech.ru/ojs/index.php/kio/article/view/1069
Выпуск
Раздел
Новая статья