Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, 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-1[/math] точек оболочки совпадают. Докажем, что и для [math]i[/math] точек они совпадут.

Рассмотрим истинную оболочку [math]ch(S \cup {i}) = ch(S) \cup i \setminus P[/math], где [math]P[/math] - множество всех точек из [math]ch(S)[/math], видимых из [math]i[/math]. Так как мы добавляли точки в нашу оболочку против часовой стрелки и так как [math]i[/math]-тая точка лежит в [math]ch(S \cup i)[/math], то [math]P[/math] состоит из нескольких подряд идущих последних добавленных в оболочку точек, и именно их мы удаляем на текущем шаге. Поэтому наша оболочка и истинная для [math]i[/math] точек совпадают.

Тогда по индукции оболочки совпадают и для [math]i = n[/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 + 1

Сложность

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

Ссылки

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

Алгоритм Эндрю

Алгоритм, очень похожий на алгоритм Грехема.

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

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

1)Сортируем все точки по х-координате.

2)Пусть самая правая точка - [math]p_1[/math]. Добавляем ее в ответ.

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

4)Добавляем в ответ [math]t[/math].

5)Делаем так, пока не дойдем до [math]p_0[/math] - самой левой точки.

6)Повторим проход 3-5 для "нижней" половины оболочки в порядке увеличения х-координаты.

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

См. доказательство алгоритма Грехема.

Псевдокод

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

Andrew(S)
  sort S[1..n] by x-coordinate backward(than by y backward)
  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])
  k++   
  sort S[k + 1..n] by x-coordinate (than by y)
  for p = k + 1..n
    while S[k - 1], S[k], S[p] has non-right orientation
      k--
    swap(S[p], S[k + 1])
  return k + 1

Сложность

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

Ссылки

• Одно предложение о нем

Алгоритм QuickHull

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

Промежуточный шаг алгоритма. Для прямой [math]p_i p_1[/math] нашли точку [math]p[/math]. Над прямыми [math]p_i p[/math] и [math]p p_1[/math] точек нет, поэтому переходим к следующей прямой [math]p_0 p_i[/math].

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

2)Возьмем все точки выше прямой [math]p_0 p_1[/math].

3)Найдем среди этого множества точку [math]p_i[/math], наиболее отдаленную от прямой (если таких несколько, взять самую правую).

4)Рекурсивно повторить шаги 2-3 для прямых [math]p_0 p_i[/math] и [math]p_i p_1[/math], пока есть точки.

5)Добавить в ответ точки [math]p_0 .. p_i .. p_1[/math], полученные в п. 3.

6)Повторить пункты 2-5 для [math]p_1 p_0[/math] (то есть для "нижней" половины).

7)Ответ - объединение списков из п. 5 для верхней и нижней половины.

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

Очевидно, что выпуклая оболочка всего множества является объединением выпуклых оболочек для верхнего и нижнего множества. Докажем, что алгоритм верно строит оболочку для верхнего множества, для правого рассуждения аналогичны. Точки [math]p_0[/math] и [math]p_1[/math] принадлежат оболочке.

• Пусть какая-то точка входит в нашу оболочку, но не должна.

Назовем эту точку [math]t[/math]. По алгоритму эта точка появилась как самая удаленная от некой прямой [math]t_1 t_2[/math]. Так как [math]t[/math] не входит в оболочку, то существует прямая [math]t_3 t_4[/math] из настоящей выпуклой оболочки, что [math]t[/math] лежит снизу от прямой. Тогда какая-то из [math]t_3[/math] и [math]t_4[/math] удалена от прямой дальше [math]t[/math], что противоречит алгоритму.

• Наоборот, пусть какой-то точки [math]t[/math] в нашей оболочке нет, а должна быть.

Пойдем вниз рекурсии в те ветки, где есть [math]t[/math]. В какой-то момент [math]t[/math] окажется внутри некоторого треугольника. Но тогда возникает противоречие с тем, что [math]t[/math] принадлежит выпуклой оболочке - противоречие.

Таким образом, наша оболочка совпадает с истинной, а значит алгоритм корректен.

Реализация

Заметим, что длина высоты, опущенная из точки [math]t[/math] на отрезок [math]ab[/math], пропорциональна векторному произведению [math][bt \cdot ba][/math], поэтому для сравнения можно использовать именно это.

Псевдокод

Inplace-реализация алгоритма. [math]S[1..n][/math] - исходное множество. [math]quick\_hull()[/math] - рекурсивная функция, находящая оболочку подмножества [math]S[/math]. В реализации в конце каждого подмножества находятся эл-ты, точно не принадлежащие оболочке.

QuickHull(S)
  find i such that S[i] has the highest x-coordinate and lowest y-coordinate 
  swap(S[1], S[i])
  find i such that S[i] has the lowest x-coordinate and lowest y-coordinate
  swap(S[n], S[i])
  k = partition1(S) // разбиваем на те эл-ты, которые лежат над прямой и на остальные
  a = quick_hull(S, 1, k)
  b = quick_hull(S, k + 1, n);
  swap(S[a..k], S[k + 1, b])
  return start + (a - 1) + (b - k - 1) 

quick_hull(S, start, end)
  find i such that S[i], S[start], S[end] has maximum value
  (a, b) = partition2(S, start, end, S[i]) //свапаем эл-ты S так, чтобы сначала были все эл-ты над прямой S[start]S[i], потом S[i]S[end], потом все остальное
  c = quick_hull(S, start, a)
  d = quick_hull(S, a + 1, b)
  swap(S[c..a], S[a + 1..d])
  return start + (a - c) + (d - b)

Сложность

Пусть время, необходимое для нахождения оболочки над некой прямой и множеством точек [math]S[/math] есть [math]T(S)[/math] Тогда [math]T(S) = O(\|S\|) + T(A \in S) + T(B \in S)[/math], где [math]A, B[/math] - множества над полученными прямыми. Отсюда видно, что в худшем случае, алгоритм тратит [math]O(n^2)[/math]. На рандомных же данных это число равно [math]O(n \log n)[/math]

Ссылки

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