Алгоритми обчислення опуклої оболонки

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

Обчислити опуклу оболонку означає, що виконане недвозначне та ефективне представлення необхідної опуклої форми. Обчислювальна складність відповідних алгоритмів зазвичай розраховується в термінах n — числа вхідних точок, та h — числа точок в опуклій оболонці.

Плоский випадок

Розглянемо загальний випадок, де вхідними даними алгоритму є скінченна невпорядкована множина точок декартової площини.

Якщо не всі точки лежать на одній прямій, їх опуклою оболонкою буде опуклий многокутник, вершини якого — це деякі точки зі вхідної множини. Найчастіше його подання є переліком вершин, відсортованих за годинниковою стрілкою або проти годинникової стрілки. В деяких випадках зручно представляти опуклий многокутник як перетин множини півплощин або півпросторів у просторовому випадку.

Нижня межа обчислювальної складності

Кожному числу ${\displaystyle x_{i}}$ відповідає точка на параболі з координатами ${\displaystyle (x_{i},x_{i}^{2})}$. Таким чином задача побудови ОО еквівалентна задачі впорядкування точок.

Для скінченої множини точок на площині нижня межа обчислювальної складності находження опуклої оболонки у вигляді опуклого многокутника є тією ж, що й в задачі сортування з подальшим зведенням. Це унаочнює такий приклад.

Для множини ${\displaystyle x_{1},\dots ,x_{n}}$ чисел, які треба відсортувати, розглянемо множину ${\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}$ точок площини. Так як, вони лежать на параболі, яка є опуклою кривою, легко бачити, що вершини опуклої оболонки, що проходяться вздовж межі, створюють відсортовану множину чисел ${\displaystyle 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 (кількістю точок опуклої оболонки). Такі алгоритми називаються алгоритмами, чутливими до вихідних даних^[en]. Вони можуть бути асимптотично ефективнішими, ніж алгоритми Θ(n log n) у випадках, коли h = o(n).

Відомо, що нижня межа часу роботи в найгіршому випадку алгоритмів чутливих до вихідних даних опуклої оболонки дорівнює Ω(n log h) у планарному випадку.^[1] Існує кілька алгоритмів, які досягають цієї оптимальної часової складності. Перший з таких алгоритмів був представлений Кіркпатріком^[en] і Зейделем^[en] у 1986 році (які назвали його «алгоритмом крайньої опуклої оболонки»). Більш простий алгоритм був розроблений Ченом^[en] у 1996 році та називається алгоритм Чена.

Алгоритми

Відомі алгоритми обчислення опуклої оболонки, наведені нижче, відсортовано за датою їх першої публікації. Обчислювальна складність кожного алгоритму наведена в термінах числа вхідних точок n і числа точок оболонки h. В найгіршому випадку h дорівнюватиме n.

• Алгоритм Джарвіса — O(nh)
  Один з найпростіших (також з найефективнішим використанням часу в найгіршому випадку) плоских алгоритмів. Винайдений Чандом і Капуром в 1970 і Р. А. Джарвісом в 1973 роках. Він має обчислювальну складність O(nh). В найгіршому випадку обчислювальна складність складає O(n²).

• Алгоритм Грехема — O(n log n)
  Дещо більш складний, але значно більш ефективний алгоритм, опублікований Рональдом Гремом в 1972 році. Якщо точки вже відсортовані за однією з координат о за кутом до фіксованого вектора, алгоритм потребує час O(n).

• Алгоритм швидкої оболонки
  Винайдений незалежно в 1977 У. Едді та в 1978 А. Бікатом. Як алгоритм швидкого сортування має очікувану складність обчислень O(n log n), але може погіршуватися до Θ(nh) = O(n²) в найгіршому випадку.

• Розділяй і володарюй — O(n log n)
  Інший O(n log n) алгоритм, опублікований в 1977 році Франко Препарата і Хонгом. Цей алгоритм є також придатним для тривимірного випадку.

• Монотонний ланцюг або Алгоритм Ендрю — O(n log n)
  Опубліковано в 1979 А. М. Ендрю. Алгоритм можна розглядати як варіант алгоритму Грехема який сортує точки в лексикографічному порядку за їх координатами. В разі, якщо вхідні точки вже відсортовані, алгоритм потребує час O(n).

• Інкрементальний алгоритм обчислення опуклої оболонки — O(n log n)
  Опубліковано в 1984 році М. Келей.

• Алгоритм Кіркпатрика — Зейделя — O(n log h)
  Перший оптимальний чутливий до вихідних даних алгоритм, він використовує техніку «шлюб перед завоюванням». Опубліковано Девідом Кіркпатріком^[en] і Реймундом Зейделем^[en] в 1986.

• Алгоритм Чена — O(n log h)
  Простіший оптимальний чутливий до вихідних даних алгоритм винайдений Тімоті Ченом^[en] в 1996 році.

Евристика Акла — Туссена

Наступна проста евристика часто використовується як перший крок у реалізації алгоритмів опуклої оболонки для підвищення їх продуктивності. Він заснований на ефективному алгоритмі опуклої оболонки Селіма Акла^[en] та Годфріда Туссена^[en], 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] Наприклад, у випадках більших розмірностей можна застосовувати алгоритм Чена і алгоритм швидкої оболонки.^[8]

Для скінченної множини точок, опукла оболонка є опуклим багатогранником в тривимірному просторі і опуклим політопом для будь-якої кількості розмірностей, чиї вершини є точками з вхідної множини точок. Його представлення не є таким простим, як в плоскому випадку. У випадку більших розмірностей, навіть якщо відомі вершини опуклого політопу, побудова його граней є нетривіальною задачею, як і задача побудови вершин при наявних гранях. Об'єм вихідних даних є експоненціально більшим за об'єм вхідних даних і навіть у випадках, коли вхідні та вихідні дані мають порівняний об'єм, відомі алгоритми обчислення опуклої оболонки для віщих розмірностей не є чутливими до вихідних^[en] даних у відношенні до питань вироджених вхідних даних і проміжних результатів високої складності.^[9]

Див. також

• Задача динамічної підтримки опуклої оболонки
• Ортогональна опукла оболонка

Примітки

1. Препарата, Шеймос, Обчислювальна геометрія, Глава «Опуклі оболонки: Базисні алгоритми»
2. Luc Devroye and Godfried Toussaint, "A note on linear expected time algorithms for finding convex hulls, " Computing, Vol. 26, 1981, pp. 361—366.
3. Aloupis, Greg. A History of Linear-time Convex Hull Algorithms for Simple Polygons. Процитовано 11 жовтня 2020.
4. McCallum, Duncan; Avis, David (1979), A linear algorithm for finding the convex hull of a simple polygon, Information Processing Letters, 9 (5): 201—206, doi:10.1016/0020-0190(79)90069-3, MR 0552534
5. Graham, Ronald L.; Yao, F. Frances (1983), Finding the convex hull of a simple polygon, Journal of Algorithms, 4 (4): 324—331, doi:10.1016/0196-6774(83)90013-5, MR 0729228
6. Lee, D. T. (1983), On finding the convex hull of a simple polygon, International Journal of Computer and Information Sciences, 12 (2): 87—98, doi:10.1007/BF00993195, MR 0724699
7. See David Mount's Конспект лекцій, в т.ч. Лекція 4 щодо останніх розробок, в т.ч. алгоритм Чена.
8. Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 грудня 1996). The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software. 22 (4): 469—483. doi:10.1145/235815.235821.
9. Avis, David; Bremner, David; Seidel, Raimund (1997), How good are convex hull algorithms?, Computational Geometry: Theory and Applications, 7 (5–6): 265—301, doi:10.1016/S0925-7721(96)00023-5.

Література

• Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. — М. : Мир, 1989. — 478 с. — ISBN 5-03-001041-6.
• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 33.3: Знаходження опуклої оболонки. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.