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

Вообразим, что плоскость - это деревянная доска, утыканная гвоздями в каждой точке из данного множества. Теперь натянем вокруг гвоздей резиновое кольцо. Оно стянется и образует выпуклую оболочку, как показано на рисунке выше.

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

Асимптотика числа вершин выпуклой оболочки для n точек,

• равномерно распределенных внутри единичного круга - Theta(n^1/3)
• равномерно распределенных внутри фиксированного выпуклого многоугольника - Theta(log n)
• подчиненных двумерному нормальному распределению - Theta((log n)^1/2)

В оценках ниже n - количество точек, h - количество точек выпуклой оболочки.

Простой многоугольник - замкнутая ломаная без самопересечений.

• Gift wrapping
  Простой алгоритм, время работы:
  • Лучший случай, все точки внутри оболочки: O(n)
  • Худший случай, все точки на оболочке: O(n²)
  • Среднее время: nh
• Graham's scan
  Алгоритм состоит из двух частей: сначала точки сортируются по полярному углу - O(nlogn). Если взять точки в порядке возрастания полярного угла, то получается простой многоугольник. Выпуклую оболочку произвольного простого многоугольника за O(n) находит вторая часть алгоритма.
• Алгоритм Мелькмана
  Находит выпуклую оболочку простого многоугольника за O(n) операций.
• Quickhull
  Рекурсивный, простой алгоритм. Время работы:
  • Лучший случай, все точки внутри оболочки: O(n)
  • Худший случай, все точки на оболочке: O(n²)
  • Среднее время: O(nlogn)
  На случайном наборе точек этот алгоритм работает быстрее всех.
• Разделяй-и-властвуй
  Вообще говоря, этот алгоритм медленнее, чем Quickhull. Но у него есть два важных преимущества:
  • Время работы всегда O(nlogn)
  • Легко распараллеливается: множество точек делится на N частей, выпуклые оболочки которых вычисляются независимо, а затем быстро сливаются.
  Существует две вариации алгоритма:

  В одной исходное множества точек разделяется на N частей, отсортированных по координате X: все точки из (k-1)-ой части левее точек из частей k..N. Этого можно достичь в процессе предобработки за O(nlogN) операций(нахождение середины: O(n)). А уже потом каждая часть вычисляется независимо(возможно, на своей машине/процессоре) и результаты объединяются.

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

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

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

Выпуклая оболочка онлайн

Алгоритмы выше принимают на вход все множество точек сразу, обрабатывают его и возвращают результат. А что, если точки подаются одна за другой, а задача состоит в том, чтобы поддерживать выпуклую оболочку имеющихся точек? Самый простой выход - после каждой добавленной точки вызывать какой-нибудь из описанных выше алгоритмов. Он построит выпуклую оболочку за Omega(nlogn) операций. Это приведет к сложности Omega(n²logn). Если хочется сделать побыстрее и поизящнее, то можно применить модифицированный алгоритм, работающий за O(n²).

Алгоритм QuickHull может быть естественным образом обобщен на случай произвольной размерности.

Трехмерный случай подробно описан в англоязычной статье, а общий, произвольной размерности, в оригинальной работе Барбера^zip