Алгоритмы вычислительной геометрии. Выпуклые оболочки: связь с задачей сортировки и оптимальные алгоритмы.
Abstract
В продолжение статьи предыдущего номера рассматриваются алгоритмы построения выпуклой оболочки на плоскости. Связь этой задачи с задачей сортировки позволяет найти нижнюю оценку сложности задачи построения выпуклой оболочки. Кроме того, аналогия между этими двумя задачами приводит к некоторым оптимальным по сложности алгоритмам построения выпуклой оболочки. Рассматриваются также алгоритмы Киркпатрика-Зайделя и Чена, асимптотическая сложность которых зависит от размера построенной выпуклой оболочки. (С. 6-18)
Published
2014-01-17
How to Cite
Симончик, С., Преображенский, А., & Ивановский, С. (2014). Алгоритмы вычислительной геометрии. Выпуклые оболочки: связь с задачей сортировки и оптимальные алгоритмы. Computer Tools in Education, (2). Retrieved from http://cte.eltech.ru/ojs/index.php/kio/article/view/1069
Issue
Section
Articles
This work is licensed under a Creative Commons Attribution 4.0 International License.