Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull

Конспект не готов.

Ниже приводятся основные алгоритмы построения выпуклых оболочек статического множества. Используются обозначения: [math]n[/math] - размер входных данных, [math]k[/math] - размер оболочки.

Алгоритм Джарвиса

По-другому "Gift wrapping algorithm" (Заворачивание подарка).

Описание Алгоритма

Промежуточный шаг алгоритма. Для точки [math]p_i[/math] ищем следующую перебором.

1) Возьмем самую правую нижнюю точку [math]p_0[/math] нашего множества. Добавляем ее в ответ.

2) На каждом следующем шаге для последнего добавленного [math]p_i[/math] ищем [math]p_{i + 1}[/math] среди всех недобавленных точек и [math]p_0[/math] с максимальным полярным углом относительно [math]p_i[/math] (Если углы равны, надо сравнивать по расстоянию). Добавляем [math]p_{i + 1}[/math] в ответ. Если [math]p_{i + 1} == p_0[/math] , заканчиваем алгоритм.

Корректность

Точка [math]p_0[/math], очевидно, принадлежит оболочке. На каждом последующем шаге алгоритма мы получаем прямую [math]p_{i-1}p_i[/math], по построению которой все точки множества лежат слева от нее. Значит, выпуклая оболочка состоит из [math]p_{i}[/math]-ых и только из них.

Псевдокод

Inplace-реализация алгоритма. [math]S[1..n][/math] - исходное множество, [math]n \gt 2[/math]

 Jarvis(S)
   find i such that S[i] has the lowest y-coordinate and highest x-coordinate
   p0 = S[i]
   pi = p0
   k = 0
   do 
     k++
     for i = k..n 
       if S[i] has lower angle and higher distance than S[k] in relation to pi
         swap(S[i], S[k])
     pi = S[k]
   while pi != p0
   return k

Сложность

Добавление каждой точки в ответ занимает [math]O(n)[/math] времени, всего точек будет [math]k[/math], поэтому итоговая сложность [math]O(nk)[/math].

Ссылки

• Английская статья — Wikipedia
• Русская статья — Wikipedia

Алгоритм Грэхема

Описание Алгоритма

Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки [math]p[/math] последовательно убираем из оболочки точки с [math]i+3[/math]-ей до [math]i+1[/math]-ой

1)Находим самую правую нижнюю точку множества [math]p_0[/math], добавляем в ответ.

2)Сортируем все остальные точки по полярному углу относительно [math]p_0[/math].

3)Добавляем в ответ [math]p_1[/math] - самую первую из отсортированных точек.

4)Берем следующую по счету точку [math]t[/math]. Пока [math]t[/math] и две последних точки в текущей оболочке [math]p_i[/math] и [math]p_{i-1}[/math] образуют неправый поворот, удаляем из оболочки [math]p_i[/math].

5)Добавляем в оболочку [math]t[/math].

6)Делаем п.5, пока не закончатся точки.

Корректность

Конспект не готов.

Докажем, что на каждом шаге множество [math]p_i[/math]-тых является выпуклой оболочкой всех уже рассмотренных точек. Доказательство проведем по индукции.

1)База. Для трех первых точек утверждение, очевидно, выполняется.

2)Переход. Предположим от противного, что утверждение на [math]i[/math]-м шаге перестает выполняться. Тогда существует два варианта:

• В нашей оболочке есть лишние точки.

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

• В нашей оболочке нет каких-то точек, которые есть в настоящей.

Удаляем мы только те 

Псевдокод

Inplace-реализация алгоритма. [math]S[1..n][/math] - исходное множество, [math]n \gt 2[/math]

Graham(S)
  find i such that S[i] has the lowest y-coordinate and highest x-coordinate
  swap(S[i], S[1])
  sort S[2..n] by angle in relation to S[1]
  k = 2
  for p = 3..n
    while S[k - 1], S[k], S[p] has non-right orientation
      k--
    swap(S[p], S[k + 1])   
  return k

Сложность

Сортировка точек занимает [math]O(n \log n)[/math] времени. При обходе каждая точка добавляется в ответ не более одного раза, поэтому сложность этой части - [math]O(n)[/math]. Суммарное время - [math]O(n \log n)[/math].

Ссылки

• Английская статья — Wikipedia
• Русская статья — Wikipedia

Алгоритм

Ссылки

• Английская статья — Wikipedia
• Русская статья — Wikipedia