Алгоритмы построения выпуклых оболочек различных объектов имеют широкий спектр приложений в математике и информатике .
В вычислительной геометрии предложены многочисленные алгоритмы вычисления выпуклой оболочки конечного набора точек с различной вычислительной сложностью .
Вычисление выпуклой оболочки означает, что строится однозначное и эффективное представление требуемой выпуклой формы. Сложность соответствующих алгоритмов обычно оценивается через n , количество входных точек, а иногда также через h , количество точек на выпуклой оболочке.
Рассмотрим общий случай, когда входными данными алгоритма является конечное неупорядоченное множество точек на декартовой плоскости. Важный частный случай, когда точки заданы в порядке обхода границы простого многоугольника, описан позже в отдельном подразделе.
Если не все точки лежат на одной прямой, то их выпуклая оболочка представляет собой выпуклый многоугольник , вершинами которого являются некоторые точки входного набора. Наиболее распространенным его представлением является список его вершин, упорядоченных вдоль его границы по или против часовой стрелки. В некоторых приложениях выпуклый многоугольник удобно представлять как пересечение набора полуплоскостей .
Легко показать, что для конечного набора точек на плоскости нижняя граница вычислительной сложности нахождения выпуклой оболочки, представленной в виде выпуклого многоугольника, такая же, как и для сортировки с использованием следующего сокращения . Для сортировки заданных чисел рассмотрим набор точек на плоскости. Поскольку они лежат на параболе , которая представляет собой выпуклую кривую , легко видеть, что вершины выпуклой оболочки при прохождении вдоль границы создают отсортированный порядок чисел . Очевидно, что для описанного преобразования чисел в точки и последующего извлечения их отсортированного порядка требуется линейное время . Поэтому в общем случае выпуклую оболочку из n точек невозможно вычислить быстрее, чем сортировку.
Стандартная нижняя граница сортировки Ω( n log n ) доказывается в модели вычислений в виде дерева решений , в которой могут выполняться только числовые сравнения, но не арифметические операции; однако в этой модели выпуклые оболочки вообще невозможно вычислить. Сортировка также требует времени Ω( n log n ) в модели вычислений в виде алгебраического дерева решений , модели, которая больше подходит для выпуклых оболочек, а в этой модели выпуклые оболочки также требуют времени Ω( n log n ). [1] Однако в моделях компьютерной арифметики, которые позволяют сортировать числа быстрее, чем за время O ( n log n ), например, с помощью алгоритмов сортировки целых чисел , плоские выпуклые оболочки также могут вычисляться быстрее: алгоритм сканирования Грэма для Выпуклая оболочка состоит из одного этапа сортировки, за которым следует линейный объем дополнительной работы.
Как указано выше, сложность поиска выпуклой оболочки в зависимости от входного размера n ограничена снизу величиной Ω( n log n ). Однако сложность некоторых алгоритмов выпуклой оболочки можно охарактеризовать как входным размером n , так и выходным размером h (количеством точек в оболочке). Такие алгоритмы называются алгоритмами, чувствительными к выходу . Они могут быть асимптотически более эффективными, чем алгоритмы Θ( n log n ) в случаях, когда h = o ( n ).
Нижняя граница времени работы чувствительных к выходу алгоритмов выпуклой оболочки в наихудшем случае была установлена как Ω( n log h ) в плоском случае. [1] Существует несколько алгоритмов, которые достигают этой оптимальной временной сложности . Самый ранний из них был предложен Киркпатриком и Зайделем в 1986 году (которые назвали его « совершенным алгоритмом выпуклой оболочки »). Гораздо более простой алгоритм был разработан Чаном в 1996 году и называется алгоритмом Чана .
Известные алгоритмы выпуклой оболочки перечислены ниже в порядке возрастания даты первой публикации. Временная сложность каждого алгоритма выражается количеством входных точек n и количеством точек на корпусе h . Обратите внимание, что в худшем случае h может достигать n .
Следующая простая эвристика часто используется в качестве первого шага в реализации алгоритмов выпуклой оболочки для повышения их производительности. Он основан на эффективном алгоритме выпуклой оболочки, разработанном Селимом Аклом и Туссеном , 1978 год. Идея состоит в том, чтобы быстро исключить множество точек, которые в любом случае не были бы частью выпуклой оболочки. Этот метод основан на следующей идее. Найдите две точки с самой низкой и самой высокой координатой X, а также две точки с самой низкой и самой высокой координатой Y. (Каждая из этих операций занимает O ( n ).) Эти четыре точки образуют выпуклый четырёхугольник , и все точки, лежащие в этом четырёхугольнике (кроме четырёх изначально выбранных вершин), не являются частью выпуклой оболочки. Поиск всех этих точек, лежащих в этом четырехугольнике, также занимает O( n ), и, следовательно, вся операция занимает O( n ). При желании точки с наименьшей и наибольшей суммами координат x и y, а также точки с наименьшей и наибольшей разницей координат x и y также могут быть добавлены к четырехугольнику, образуя таким образом неправильный выпуклый восьмиугольник, внутренние части которого могут быть безопасно выброшены. Если точки являются случайными величинами, то для узкого, но часто встречающегося класса функций плотности вероятности этот одноразовый шаг предварительной обработки заставит алгоритм выпуклой оболочки работать за линейное ожидаемое время, даже если сложность выпуклой функции в наихудшем случае Алгоритм Халла квадратичен по n . [2]
В приведенном выше обсуждении рассматривается случай, когда все входные точки известны заранее. Можно рассмотреть еще два параметра. [1]
Вставка точки может увеличить количество вершин выпуклой оболочки не более чем на 1, а удаление может превратить n -вершинную выпуклую оболочку в n-1 -вершинную.
Онлайн-версия может обрабатываться с помощью O(log n ) на точку, что является асимптотически оптимальным. Динамическая версия может обрабатываться с помощью O(log 2 n ) за операцию. [1]
Выпуклая оболочка простого многоугольника разбивается многоугольником на части, одна из которых — сам многоугольник, а остальные — карманы , ограниченные частью границы многоугольника и одним ребром оболочки. Хотя для задачи построения выпуклой оболочки простого многоугольника опубликовано множество алгоритмов, почти половина из них неверны. [3] МакКаллум и Авис предоставили первый правильный алгоритм. [4] Более позднее упрощение, предложенное Грэмом и Яо (1983) и Ли (1983), использует только одну структуру данных стека . Их алгоритм обходит многоугольник по часовой стрелке, начиная с его крайней левой вершины. При этом он сохраняет в стеке выпуклую последовательность вершин, тех, которые еще не были идентифицированы как находящиеся внутри карманов. На каждом шаге алгоритм следует по пути вдоль многоугольника от вершины стека до следующей вершины, которая не находится ни в одном из двух карманов, соседних с вершиной стека. Затем, хотя две верхние вершины стека вместе с этой новой вершиной не находятся в выпуклом положении, он извлекает стек, прежде чем окончательно поместить новую вершину в стек. Когда обход по часовой стрелке достигает начальной точки, алгоритм возвращает последовательность вершин стека в качестве оболочки. [5] [6]
Известен ряд алгоритмов как для трехмерного случая, так и для произвольных размерностей. [7] Алгоритм Чана используется для измерений 2 и 3, а Quickhull используется для расчета выпуклой оболочки в более высоких измерениях. [8]
Для конечного набора точек выпуклая оболочка представляет собой выпуклый трехмерный многогранник или, вообще, выпуклый многогранник для любого количества измерений, вершинами которого являются некоторые точки входного набора. Однако его представление не так просто, как в плоском случае. В более высоких размерностях, даже если вершины выпуклого многогранника известны, построение его граней является нетривиальной задачей, как и двойственная задача построения вершин по граням. Размер выходной информации о грани может быть экспоненциально больше, чем размер входных вершин, и даже в случаях, когда входные и выходные данные имеют сопоставимый размер, известные алгоритмы для многомерных выпуклых оболочек не чувствительны к выходным данным как из-за проблемы с вырожденными входными данными и промежуточными результатами высокой сложности. [9]
