Алгоритмы выпуклой оболочки

Алгоритмы построения выпуклых оболочек различных объектов имеют широкий спектр приложений в математике и информатике .

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

Вычисление выпуклой оболочки означает, что строится однозначное и эффективное представление требуемой выпуклой формы. Сложность соответствующих алгоритмов обычно оценивается через n , количество входных точек, а иногда также через h , количество точек на выпуклой оболочке.

Плоский случай [ править ]

Рассмотрим общий случай, когда входными данными алгоритма является конечное неупорядоченное множество точек на декартовой плоскости. Важный частный случай, когда точки заданы в порядке обхода границы простого многоугольника, описан позже в отдельном подразделе.

Если не все точки лежат на одной прямой, то их выпуклая оболочка представляет собой выпуклый многоугольник, вершинами которого являются некоторые точки входного набора. Наиболее распространенным его представлением является список его вершин, упорядоченных вдоль его границы по или против часовой стрелки. В некоторых приложениях выпуклый многоугольник удобно представлять как пересечение набора полуплоскостей .

граница сложности Нижняя вычислительной

Легко показать, что для конечного набора точек на плоскости нижняя граница вычислительной сложности нахождения выпуклой оболочки, представленной в виде выпуклого многоугольника, такая же, как и для сортировки с использованием следующего сокращения . Для набора $x_{1},\dots ,x_{n}$ числа для сортировки рассмотрим набор $(x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})$ точек на плоскости. Поскольку они лежат на параболе , которая представляет собой выпуклую кривую , легко видеть, что вершины выпуклой оболочки при прохождении вдоль границы создают отсортированный порядок чисел $x_{1},\dots ,x_{n}$ . Очевидно, что линейное время для описанного преобразования чисел в точки и последующего извлечения их отсортированного порядка требуется . Поэтому в общем случае выпуклую оболочку из 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 .

Подарочная упаковка , она же марш Джарвиса — О ( нх )
Один из самых простых (хотя и не самый эффективный по времени в худшем случае) планарных алгоритмов. Создан независимо Чандом и Капуром в 1970 году и Р.А. Джарвисом в 1973 году. Он имеет O ( nh ) временную сложность , где n — количество точек в наборе, а h — количество точек в оболочке. В худшем случае сложность составит O ( n ²).
Сканирование Грэма — O ( n log n )
Немного более сложный, но гораздо более эффективный алгоритм, опубликованный Рональдом Грэмом в 1972 году. Если точки уже отсортированы по одной из координат или по углу к фиксированному вектору, то алгоритм занимает O( n ). время
Квикхалл
Создан независимо в 1977 г. У. Эдди и в 1978 г. А. Быкатом. Как и алгоритм быстрой сортировки , он имеет ожидаемую временную сложность O ( n log n ), но может выродиться до O ( n ²) в худшем случае.
Разделяй и властвуй — O ( n log n )
Другой O( n log n алгоритм ), опубликованный в 1977 году компаниями Preparata и Hong. Этот алгоритм применим и к трехмерному случаю.
Монотонная цепочка , она же алгоритм Эндрю — O ( n log n )
Опубликовано в 1979 году А. М. Эндрю. Алгоритм можно рассматривать как вариант сканирования Грэма, который лексикографически сортирует точки по их координатам. Когда входные данные уже отсортированы, алгоритм занимает время O ( n ).
Алгоритм инкрементальной выпуклой оболочки — O ( n log n )
Опубликовано в 1984 году Майклом Каллаем.
Алгоритм Киркпатрика – Зейделя — O ( n log h )
Первый оптимальный алгоритм, чувствительный к выходу. Он модифицирует алгоритм «разделяй и властвуй», используя технику «брак до завоевания» и низкоразмерное линейное программирование . Опубликовано Киркпатриком и Зайделем в 1986 году.
Алгоритм Чана — O ( n log h )
Более простой оптимальный алгоритм, чувствительный к выходным данным, созданный Чаном в 1996 году. Он сочетает в себе подарочную упаковку с выполнением алгоритма O ( n log 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 ² n ) за операцию. ^[1]

Простой многоугольник [ править ]

Выпуклая оболочка простого многоугольника разбивается многоугольником на части, одна из которых — сам многоугольник, а остальные — карманы , ограниченные частью границы многоугольника и одним ребром оболочки. Хотя для задачи построения выпуклой оболочки простого многоугольника опубликовано множество алгоритмов, почти половина из них неверны. ^[3] МакКаллум и Авис предложили первый правильный алгоритм. ^[4]Более позднее упрощение, предложенное Грэмом и Яо (1983) и Ли (1983), использует только одну структуру данных стека . Их алгоритм обходит многоугольник по часовой стрелке, начиная с его крайней левой вершины. При этом он сохраняет в стеке выпуклую последовательность вершин, тех, которые еще не идентифицированы как находящиеся внутри карманов. На каждом шаге алгоритм следует по пути вдоль многоугольника от вершины стека до следующей вершины, которая не находится ни в одном из двух карманов, соседних с вершиной стека. Затем, хотя две верхние вершины стека вместе с этой новой вершиной не находятся в выпуклом положении, он извлекает стек, прежде чем окончательно поместить новую вершину в стек. Когда обход по часовой стрелке достигает начальной точки, алгоритм возвращает последовательность вершин стека в качестве оболочки. ^[5]^[6]

Высшие измерения [ править ]

Известен ряд алгоритмов как для трехмерного случая, так и для произвольных размерностей. ^[7] Алгоритм Чана используется для измерений 2 и 3, а Quickhull используется для расчета выпуклой оболочки в более высоких измерениях. ^[8]

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

См. также [ править ]

Ортогональная выпуклая оболочка

Ссылки [ править ]

^ Перейти обратно: ^а ^б ^с ^д Препарата, Шамос, Вычислительная геометрия , Глава «Выпуклые оболочки: основные алгоритмы»
^ Люк Деврой и Годфрид Туссен , «Заметка об алгоритмах линейного ожидаемого времени для поиска выпуклых оболочек», Computing , Vol. 26, 1981, стр. 361–366.
^ Алупис, Грег. «История алгоритмов выпуклой оболочки, работающих за линейное время для простых многоугольников» . Проверено 11 октября 2020 г.
^ МакКаллум, Дункан; Авис, Дэвид (1979), «Линейный алгоритм поиска выпуклой оболочки простого многоугольника», Information Processing Letters , 9 (5): 201–206, doi : 10.1016/0020-0190(79)90069-3 , MR 0552534
^ Грэм, Рональд Л .; Яо, Ф. Фрэнсис (1983), «Нахождение выпуклой оболочки простого многоугольника», Journal of Algorithms , 4 (4): 324–331, doi : 10.1016/0196-6774(83)90013-5 , MR 0729228
^ Ли, Д.Т. (1983), «О поиске выпуклой оболочки простого многоугольника», Международный журнал компьютерных и информационных наук , 12 (2): 87–98, doi : 10.1007/BF00993195 , MR 0724699 , S2CID 28600832
^ См. Дэвида Маунта , конспекты лекций включая лекцию 4, о последних событиях, в том числе Алгоритм Чана .
^ Барбер, К. Брэдфорд; Добкин, Дэвид П.; Хухданпаа, Ханну (1 декабря 1996 г.). «Алгоритм Quickhull для выпуклых оболочек» (PDF) . Транзакции ACM в математическом программном обеспечении . 22 (4): 469–483. дои : 10.1145/235815.235821 .
^ Авис, Дэвид ; Бремнер, Дэвид; Зайдель, Раймунд (1997), «Насколько хороши алгоритмы выпуклой оболочки?», Вычислительная геометрия: теория и приложения , 7 (5–6): 265–301, doi : 10.1016/S0925-7721(96)00023-5 .

Дальнейшее чтение [ править ]

Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 33.3: Нахождение выпуклой оболочки, стр. 947–957.
Франко П. Препарата , С.Дж. Хонг . Выпуклые оболочки конечных множеств точек в двух и трех измерениях , Сообщ. АКМ, том. 20, нет. 2, стр. 87–93, 1977.
Марк де Берг ; Марк ван Кревелд ; Марк Овермарс и Отфрид Шварцкопф (2000). Вычислительная геометрия (2-е исправленное изд.). Издательство Спрингер . ISBN 978-3-540-65620-3 . Раздел 1.1: Пример: выпуклые оболочки (описывает классические алгоритмы для двумерных выпуклых оболочек). Глава 11: Выпуклые оболочки: стр. 235–250 (описывается рандомизированный алгоритм для трехмерных выпуклых оболочек, предложенный Кларксоном и Шором).

Внешние ссылки [ править ]

Вайсштейн, Эрик В. «Выпуклая оболочка» . Математический мир .
Выпуклая оболочка 2D, 3D и dD в CGAL , библиотеке алгоритмов вычислительной геометрии
Код Кхалла для выпуклой оболочки, триангуляции Делоне, диаграммы Вороного и пересечения полупространств
Демонстрация алгоритмов Flash SWF, Джарвиса, Грэма, Квик (разделяй и властвуй) и Чана.
Алгоритм упаковки подарков на C#

[ps-1] Перейти обратно: ^а ^б ^с ^д Препарата, Шамос, Вычислительная геометрия , Глава «Выпуклые оболочки: основные алгоритмы»

[2] Люк Деврой и Годфрид Туссен , «Заметка об алгоритмах линейного ожидаемого времени для поиска выпуклых оболочек», Computing , Vol. 26, 1981, стр. 361–366.

[3] Алупис, Грег. «История алгоритмов выпуклой оболочки, работающих за линейное время для простых многоугольников» . Проверено 11 октября 2020 г.

[4] МакКаллум, Дункан; Авис, Дэвид (1979), «Линейный алгоритм поиска выпуклой оболочки простого многоугольника», Information Processing Letters , 9 (5): 201–206, doi : 10.1016/0020-0190(79)90069-3 , MR 0552534

[5] Грэм, Рональд Л .; Яо, Ф. Фрэнсис (1983), «Нахождение выпуклой оболочки простого многоугольника», Journal of Algorithms , 4 (4): 324–331, doi : 10.1016/0196-6774(83)90013-5 , MR 0729228

[6] Ли, Д.Т. (1983), «О поиске выпуклой оболочки простого многоугольника», Международный журнал компьютерных и информационных наук , 12 (2): 87–98, doi : 10.1007/BF00993195 , MR 0724699 , S2CID 28600832

[7] См. Дэвида Маунта , конспекты лекций включая лекцию 4, о последних событиях, в том числе Алгоритм Чана .

[8] Барбер, К. Брэдфорд; Добкин, Дэвид П.; Хухданпаа, Ханну (1 декабря 1996 г.). «Алгоритм Quickhull для выпуклых оболочек» (PDF) . Транзакции ACM в математическом программном обеспечении . 22 (4): 469–483. дои : 10.1145/235815.235821 .

[9] Авис, Дэвид ; Бремнер, Дэвид; Зайдель, Раймунд (1997), «Насколько хороши алгоритмы выпуклой оболочки?», Вычислительная геометрия: теория и приложения , 7 (5–6): 265–301, doi : 10.1016/S0925-7721(96)00023-5 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]