Статья

В статье рассматриваются алгоритмы вычисления выпуклой оболочки на плоскости. Приведены примеры использования выпуклых оболочек в разных задачах: от интеллектуального анализа данных до расчета топологии беспроводной сети. Показана работа двух классических алгоритмов вычисления выпуклой оболочки: сканирование по Грэхему и обход по Джарвису. Приведен алгоритм сканирования по Грэхему. Рассмотрены его специфические особенности применительно к выбору начальной точки, значений углов, приведена оценка вычислительной сложности. Показаны особенности обхода по Джарвису, в основе которого расчет выпуклой оболочки осуществляется на основе ребер, а не вершин. Показана аналогия работы алгоритма по Джарвису на основе метода упаковки пакета, а также вариации реализации с использованием разнонаправленных цепей и без них.