:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » Выпуклая оболочка
  Построение выпуклой оболочки конечного множества точек



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

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

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

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

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

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

  Алгоритмы 2D



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

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

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

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

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

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

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

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

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


  Алгоритм 3D



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

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