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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм Эндрю)
(Ссылки)
(не показано 39 промежуточных версий 11 участников)
Строка 1: Строка 1:
{{notready}}
+
 
 +
{{ready}}
 +
{{Определение
 +
|definition=Выпуклой оболочкой множества точек называется пересечение всех выпуклых множеств, содержащих все заданные точки.}}
 +
 
 
Ниже приводятся основные алгоритмы построения выпуклых оболочек статического множества. Используются обозначения: <tex>n</tex> - размер входных данных, <tex>k</tex> - размер оболочки.
 
Ниже приводятся основные алгоритмы построения выпуклых оболочек статического множества. Используются обозначения: <tex>n</tex> - размер входных данных, <tex>k</tex> - размер оболочки.
  
Строка 5: Строка 9:
  
 
По-другому "Gift wrapping algorithm" (Заворачивание подарка).
 
По-другому "Gift wrapping algorithm" (Заворачивание подарка).
 +
Он заключается в том, что мы ищем выпуклую оболочку последовательно, против часовой стрелки, начиная с определенной точки.
  
 
== Описание Алгоритма ==
 
== Описание Алгоритма ==
[[File:Graham1.png|right|250px|Промежуточный шаг алгоритма]] <br/><br/>
+
[[File:Graham1.png|thumb|250px|Промежуточный шаг алгоритма. Для точки <tex>p_i</tex> ищем следующую перебором.]] <br/><br/>
1) Возьмем самую правую нижнюю точку <tex>p_0</tex> нашего множества. Добавляем ее в ответ.
+
# Возьмем точку <tex>p_0</tex> нашего множества с самой маленькой у-координатой (если таких несколько, берем самую правую из них). Добавляем ее в ответ.
 +
# На каждом следующем шаге для последнего добавленного <tex>p_i</tex> ищем <tex>p_{i + 1}</tex> среди всех недобавленных точек и <tex>p_0</tex> {{Acronym|с максимальным полярным углом относительно <tex>p_i</tex> (Если углы равны, надо сравнивать по расстоянию)|Считать углы не нужно, можно просто подставить в функцию сравнения предикат поворота}}. Добавляем <tex>p_{i + 1}</tex> в ответ. Если <tex>p_{i + 1} == p_0</tex> , заканчиваем алгоритм.
  
2) На каждом следующем шаге для последнего добавленного <tex>p_i</tex> ищем <tex>p_{i + 1}</tex> среди всех недобавленных точек и <tex>p_0</tex> с максимальным полярным углом относительно <tex>p_i</tex> (Если углы равны, надо сравнивать по расстоянию). Добавляем <tex>p_{i + 1}</tex> в ответ. Если <tex>p_{i + 1} == p_0</tex> , заканчиваем алгоритм.
 
  
  
 +
<br/><br/><br/><br/>
  
<br/><br/><br/><br/>
 
 
== Корректность ==
 
== Корректность ==
  
Строка 21: Строка 26:
 
== Псевдокод ==
 
== Псевдокод ==
  
Inplace-реализация алгоритма. <tex>S[1..n]</tex> - исходное множество.
+
Inplace-реализация алгоритма. <tex>S[1..n]</tex> - исходное множество, <tex>n > 2</tex>
  
 
   Jarvis(S)
 
   Jarvis(S)
Строка 39: Строка 44:
 
== Сложность ==
 
== Сложность ==
  
Добавление каждой точки в ответ занимает <tex>O(n)</tex> времени, всего точек будет <tex>k</tex>, поэтому итоговая сложность <tex>O(nk)</tex>.
+
Добавление каждой точки в ответ занимает <tex>O(n)</tex> времени, всего точек будет <tex>k</tex>, поэтому итоговая сложность <tex>O(nk)</tex>. В худшем случае, когда оболочка состоит из всех точек сложность <tex>O(n^2)</tex>.
  
 
== Ссылки ==
 
== Ссылки ==
Строка 47: Строка 52:
  
 
= Алгоритм Грэхема =
 
= Алгоритм Грэхема =
 +
 +
Алгоритм заключается в том, что мы ищем точки оболочки последовательно, используя стек.
  
 
== Описание Алгоритма ==
 
== Описание Алгоритма ==
  
[[File:Temp.gif|thumb|250px|Промежуточный шаг алгоритма]]
+
[[File:Graham2.png|thumb|400px|Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки <tex>p</tex> последовательно убираем из оболочки точки с <tex>i+3</tex>-ей до <tex>i+1</tex>-ой]]
1)Находим самую правую нижнюю точку множества <tex>p_0</tex>, добавляем в ответ.
+
 
2)Сортируем все остальные точки по полярному углу относительно <tex>p_0</tex>.
+
# Находим точку <tex>p_0</tex> нашего множества с самой маленькой у-координатой (если таких несколько, берем самую правую из них), добавляем в ответ.
3)Добавляем в ответ <tex>p_1</tex> - самую первую из отсортированных точек.
+
# Сортируем все остальные точки {{Acronym|по полярному углу относительно <tex>p_0</tex>|Сортировка с компаратором 'Предикат поворота'}}.
4)Берем следующую по счету точку в массиве <tex>t</tex>. Пока <tex>t</tex> и две последних точке в ответе образуют неправый поворот, удаляем из ответа последнюю точку.
+
# Добавляем в ответ <tex>p_1</tex> - самую первую из отсортированных точек.
5)Делаем п.4, пока не закончатся точки.  
+
# Берем следующую по счету точку <tex>t</tex>. Пока <tex>t</tex> и две последних точки в текущей оболочке <tex>p_i</tex> и <tex>p_{i-1}</tex> образуют неправый поворот (вектора <tex>p_i t</tex> и <tex>p_{i-1} p_i</tex>), удаляем из оболочки <tex>p_i</tex>.
 +
# Добавляем в оболочку <tex>t</tex>.
 +
# Делаем п.5, пока не закончатся точки.
  
 
== Корректность ==
 
== Корректность ==
  
 +
Докажем, что на каждом шаге множество <tex>p_i</tex>-тых является выпуклой оболочкой всех уже рассмотренных точек. Доказательство проведем по индукции.
 +
 +
* База. Для трех первых точек утверждение, очевидно, выполняется.
 +
 +
* Переход. Пусть для <tex>i-1</tex> точек оболочки совпадают. Докажем, что и для <tex>i</tex> точек они совпадут.
 +
 +
Рассмотрим истинную оболочку <tex>ch(S \cup {i}) = ch(S) \cup i \setminus P</tex>, где <tex>P</tex> - множество всех точек из <tex>ch(S)</tex>, видимых из <tex>i</tex>. Так как мы добавляли точки в нашу оболочку против часовой стрелки и так как <tex>i</tex>-тая точка лежит в <tex>ch(S \cup i)</tex>, то <tex>P</tex> состоит из нескольких подряд идущих последних добавленных в оболочку точек, и именно их мы удаляем на текущем шаге. Поэтому наша оболочка и истинная для <tex>i</tex> точек совпадают.
 +
 +
Тогда по индукции оболочки совпадают и для <tex>i = n</tex>.
  
 
== Псевдокод ==
 
== Псевдокод ==
  
Подаем в функцию исходное множество S, возвращаем позицию <tex>k</tex> - в <tex>S[1..k - 1]</tex> будет хранится наша оболочка.
+
Inplace-реализация алгоритма. <tex>S[1..n]</tex> - исходное множество, <tex>n > 2</tex>
<tex>turn(a, b, c)</tex> - модифицированная функция поворота, учитывающая случай, когда точки лежат на одной прямой.
+
 +
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 and k > 1
 +
      k--
 +
    swap(S[p], S[k + 1])
 +
    k++
 +
  return k + 1
  
 +
== Сложность ==
  
== Сложность ==
+
Сортировка точек занимает <tex>O(n \log n)</tex> времени. При обходе каждая точка добавляется в ответ не более одного раза, поэтому сложность этой части - <tex>O(n)</tex>. Суммарное время — <tex>O(n \log n)</tex>.
 +
 
 +
== Ссылки ==
  
Сортировка точек занимает <tex>O(n log n)</tex> времени. При обходе каждая точка добавляется в ответ не более одного раза, поэтому сложность этой части - <tex>O(n)</tex>. Суммарное время - <tex>O(n log n)</tex>.
+
* [http://en.wikipedia.org/wiki/Graham_scan Английская статья — Wikipedia]
 +
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%93%D1%80%D1%8D%D1%85%D0%B5%D0%BC%D0%B0 Русская статья — Wikipedia]
  
 +
= Алгоритм Эндрю =
  
= Алгоритм =
+
Алгоритм, очень похожий на алгоритм Грехема. Он заключается в том, что мы находим самую левую и самую правую точки, ищем для точек над и под этой прямой выпуклую оболочку Грехемом - {{Acronym|для них начальные точки будут лежать на <tex>\pm inf</tex>, а сортировка по углу относительно далекой точки аналогична сортировке по координате|в этом легко убедиться, подставив в предикат поворота точку с 'бесконечно' координатой}}; после этого объединяем две оболочки в одну.
  
 
== Описание Алгоритма ==
 
== Описание Алгоритма ==
 +
[[File:andrew1.png|thumb|400px|Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки <tex>p</tex> последовательно убираем из оболочки точки с <tex>i+3</tex>-ей до <tex>i+1</tex>-ой]]
 +
# Находим самую левую и самую правую точки множества - <tex>p_0</tex> и <tex>p_1</tex>.
 +
# Делим множество на две части: точки над и под прямой.
 +
# Для каждой половины ищем выпуклую оболочку Грехемом с условием, что сортируем не по полярному углу, а по координате.
 +
# Сливаем получившиеся оболочки.
 +
 +
<br/>
  
 
== Корректность ==
 
== Корректность ==
 +
 +
<br/>
 +
См. доказательство алгоритма Грехема.
 +
<br/>
  
 
== Псевдокод ==
 
== Псевдокод ==
 +
 +
Inplace-реализация алгоритма. <tex>S[1..n]</tex> - исходное множество, <tex>n > 2</tex>
 +
 +
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
 +
 +
== Сложность ==
 +
 +
Сортировка точек занимает <tex>O(n \log n)</tex> времени. При обходе каждая точка добавляется в ответ не более одного раза, поэтому сложность двух обходов - <tex> 2 \cdot O(n)</tex>. Суммарное время - <tex>O(n \log n)</tex>. Также можно отметить тот факт, что Эндрю в целом работает быстрее чем Грэхем, так как использует всего <tex>O(n)</tex> поворотов, в то время как Грэхем использует <tex>O(n \log n)</tex> поворотов.
 +
 +
== Ссылки ==
 +
 +
* [http://en.wikipedia.org/wiki/Graham_scan#Notes Одно предложение о нем]
 +
* [https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain Имплементация на 13 языках]
 +
 +
= Алгоритм Чена =
 +
 +
Является комбинацией двух алгоритмов - Джарвиса и Грехема. Недостатком Грэхема является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени <tex>O(n \log n)</tex>. Джарвис требует перебора всех точек для каждой из <tex>k</tex> точек оболочки, что в худшем случае занимает <tex>O(n^2)</tex>.
 +
 +
== Описание Алгоритма ==
 +
 +
# Разобьем все множество на произвольные группы по <tex>m</tex> штук в каждой. Будем считать, что <tex>m</tex> нам известно. Тогда всего групп окажется <tex>r = n / m</tex>.
 +
# Для каждой группы запускаем Грехема.
 +
# Начиная с самой нижней точки ищем саму выпуклую оболочку Джарвисом, но перебираем не все точки, а по одной из каждой группы.
  
 
== Сложность ==
 
== Сложность ==
 +
 +
На втором шаге алгоритма в каждой группе оболочка ищется за <tex>O(m \log m)</tex>, общее время - <tex>O(r m \log m) = O(n \log m)</tex>. На третьем шаге поиск каждой следующей точки в каждой группе занимает <tex>O(\log m)</tex>, так как точки уже отсортированы, и мы можем найти нужную бинпоиском. Тогда поиск по всем группам займет <tex dpi="130">O(r \log m) = O(\frac{n}{m} \log m)</tex>. Всего таких шагов будет <tex>k</tex>, значит общее время - <tex dpi="130">O(\frac{kn}{m} \log m)</tex>.
 +
Итоговое время - <tex>O(n (1 + \frac{k}{m}) \log m)</tex>. Несложно видеть, что минимум достигается при <tex>m = k</tex>. В таком случае сложность равна <tex>O(n \log k)</tex>.
 +
 +
== Поиск <tex>m</tex> ==
 +
 +
Как заранее узнать <tex>k</tex>? Воспользуемся следующим методом. Положим <tex>m = 2^{2^t}</tex>. Начиная с маленьких <tex>m</tex> будем запускать наш алгоритм, причем если на третьем шаге Джарвис уже сделал <tex>m</tex> шагов, то мы выбрали наше <tex>m</tex> слишком маленьким, будем увеличивать, пока не станет <tex>m \ge k</tex>.
 +
Тогда общее время алгоритма - <tex> \sum_{t=0}^{O(\log\log k)} O\left(n \log(2^{2^t})\right) = O(n) \sum_{t=0}^{O(\log\log k)} O(2^t) = O\left(n \cdot 2^{1+O(\log\log k)}\right) = O(n \log k).</tex>
  
 
== Ссылки ==
 
== Ссылки ==
  
* [http://en.wikipedia.org/wiki/Gift_wrapping_algorithm Английская статья — Wikipedia]
+
* [http://en.wikipedia.org/wiki/Chan%27s_algorithm Английская статья — Wikipedia]
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81%D0%B0 Русская статья — Wikipedia]
+
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A7%D0%B0%D0%BD%D0%B0 Русская статья — Wikipedia]
  
= Алгоритм Эндрю =
+
= Алгоритм QuickHull =
  
 
== Описание Алгоритма ==
 
== Описание Алгоритма ==
 +
[[File:hull.png|thumb|250px|Промежуточный шаг алгоритма. Для прямой <tex>p_i p_1</tex> нашли точку <tex>p</tex>. Над прямыми <tex>p_i p</tex> и <tex>p p_1</tex> точек нет, поэтому переходим к следующей прямой <tex>p_0 p_i</tex>.]]
 +
 +
# Найдем самую левую точку <tex>p_0</tex> и самую правую точку <tex>p_1</tex> (Если таких несколько, выберем среди таких нижнюю и верхнюю соответственно).
 +
# Возьмем все точки выше прямой <tex>p_0 p_1</tex>.
 +
# Найдем среди этого множества точку <tex>p_i</tex>, наиболее отдаленную от прямой (если таких несколько, взять самую правую).
 +
# Рекурсивно повторить шаги 2-3 для прямых <tex>p_0 p_i</tex> и <tex>p_i p_1</tex>, пока есть точки.
 +
# Добавить в ответ точки <tex>p_0 .. p_i .. p_1</tex>, полученные в п. 3.
 +
# Повторить пункты 2-5 для <tex>p_1 p_0</tex> (то есть для "нижней" половины).
 +
# Ответ - объединение списков из п. 5 для верхней и нижней половины.
 +
 +
<br/><br/>
  
 
== Корректность ==
 
== Корректность ==
 +
 +
[[File:hull1.png|thumb|200px|]]
 +
 +
Очевидно, что выпуклая оболочка всего множества является объединением выпуклых оболочек для верхнего и нижнего множества. Докажем, что алгоритм верно строит оболочку для верхнего множества, для нижнего рассуждения аналогичны.
 +
Точки <tex>p_0</tex> и <tex>p_1</tex> принадлежат оболочке.
 +
 +
* Пусть какая-то точка входит в нашу оболочку, но не должна.
 +
 +
Назовем эту точку <tex>t</tex>. По алгоритму эта точка появилась как самая удаленная от некой прямой <tex>t_1 t_2</tex>. Так как <tex>t</tex> не входит в оболочку, то существует прямая <tex>t_3 t_4</tex> из настоящей выпуклой оболочки, что <tex>t</tex> лежит снизу от прямой. Тогда какая-то из <tex>t_3</tex> и <tex>t_4</tex> удалена от прямой дальше <tex>t</tex>, что противоречит алгоритму.
 +
 +
* Наоборот, пусть какой-то точки <tex>t</tex> в нашей оболочке нет, а должна быть.
 +
 +
Пойдем вниз рекурсии в те ветки, где есть <tex>t</tex>. В какой-то момент <tex>t</tex> окажется внутри некоторого треугольника. Но тогда возникает противоречие с тем, что <tex>t</tex> принадлежит выпуклой оболочке.
 +
 +
Таким образом, наша оболочка совпадает с истинной, а значит алгоритм корректен.
 +
 +
== Реализация ==
 +
 +
Заметим, что длина высоты, опущенная из точки <tex>t</tex> на отрезок <tex>ab</tex>, пропорциональна векторному произведению <tex>[bt \cdot ba]</tex>, поэтому для сравнения можно использовать именно это. Векторное произведение эквивалентно предикату поворота, поэтому можно так же использовать и его.
  
 
== Псевдокод ==
 
== Псевдокод ==
 +
 +
Inplace-реализация алгоритма. <tex>S[1..n]</tex> - исходное множество. <tex>quick\_hull()</tex> - рекурсивная функция, находящая оболочку подмножества <tex>S</tex>. В реализации в конце каждого подмножества находятся эл-ты, точно не принадлежащие оболочке.
 +
 +
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) <br/>
 +
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)
  
 
== Сложность ==
 
== Сложность ==
 +
 +
Пусть время, необходимое для нахождения оболочки над некой прямой и множеством точек <tex>S</tex> есть <tex>T(S)</tex>
 +
Тогда <tex>T(S) = O(\|S\|) + T(A \in S) + T(B \in S)</tex>, где <tex>A, B</tex> - множества над полученными прямыми. Отсюда видно, что в худшем случае, алгоритм тратит <tex>O(n^2)</tex>. На рандомных же данных это число равно <tex>O(n \log n)</tex>
  
 
== Ссылки ==
 
== Ссылки ==
  
* [http://en.wikipedia.org/wiki/Gift_wrapping_algorithm Английская статья — Wikipedia]
+
* [http://en.wikipedia.org/wiki/QuickHull Английская статья — Wikipedia]
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81%D0%B0 Русская статья — Wikipedia]
 
 
 
= Алгоритм Чена =
 
= Алгоритм QuickHull =
 

Версия 18:07, 8 апреля 2018

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


Ниже приводятся основные алгоритмы построения выпуклых оболочек статического множества. Используются обозначения: [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]. В худшем случае, когда оболочка состоит из всех точек сложность [math]O(n^2)[/math].

Ссылки

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

Алгоритм заключается в том, что мы ищем точки оболочки последовательно, используя стек.

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

Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки [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 t[/math] и [math]p_{i-1} p_i[/math]), удаляем из оболочки [math]p_i[/math].
  5. Добавляем в оболочку [math]t[/math].
  6. Делаем п.5, пока не закончатся точки.

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

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

  • База. Для трех первых точек утверждение, очевидно, выполняется.
  • Переход. Пусть для [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 and k > 1
      k--
    swap(S[p], S[k + 1])  
    k++ 
  return k + 1

Сложность

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

Ссылки

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

Алгоритм, очень похожий на алгоритм Грехема. Он заключается в том, что мы находим самую левую и самую правую точки, ищем для точек над и под этой прямой выпуклую оболочку Грехемом - для них начальные точки будут лежать на [math]\pm inf[/math], а сортировка по углу относительно далекой точки аналогична сортировке по координате; после этого объединяем две оболочки в одну.

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

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


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


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

Псевдокод

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]. Также можно отметить тот факт, что Эндрю в целом работает быстрее чем Грэхем, так как использует всего [math]O(n)[/math] поворотов, в то время как Грэхем использует [math]O(n \log n)[/math] поворотов.

Ссылки

Алгоритм Чена

Является комбинацией двух алгоритмов - Джарвиса и Грехема. Недостатком Грэхема является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени [math]O(n \log n)[/math]. Джарвис требует перебора всех точек для каждой из [math]k[/math] точек оболочки, что в худшем случае занимает [math]O(n^2)[/math].

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

  1. Разобьем все множество на произвольные группы по [math]m[/math] штук в каждой. Будем считать, что [math]m[/math] нам известно. Тогда всего групп окажется [math]r = n / m[/math].
  2. Для каждой группы запускаем Грехема.
  3. Начиная с самой нижней точки ищем саму выпуклую оболочку Джарвисом, но перебираем не все точки, а по одной из каждой группы.

Сложность

На втором шаге алгоритма в каждой группе оболочка ищется за [math]O(m \log m)[/math], общее время - [math]O(r m \log m) = O(n \log m)[/math]. На третьем шаге поиск каждой следующей точки в каждой группе занимает [math]O(\log m)[/math], так как точки уже отсортированы, и мы можем найти нужную бинпоиском. Тогда поиск по всем группам займет [math]O(r \log m) = O(\frac{n}{m} \log m)[/math]. Всего таких шагов будет [math]k[/math], значит общее время - [math]O(\frac{kn}{m} \log m)[/math]. Итоговое время - [math]O(n (1 + \frac{k}{m}) \log m)[/math]. Несложно видеть, что минимум достигается при [math]m = k[/math]. В таком случае сложность равна [math]O(n \log k)[/math].

Поиск [math]m[/math]

Как заранее узнать [math]k[/math]? Воспользуемся следующим методом. Положим [math]m = 2^{2^t}[/math]. Начиная с маленьких [math]m[/math] будем запускать наш алгоритм, причем если на третьем шаге Джарвис уже сделал [math]m[/math] шагов, то мы выбрали наше [math]m[/math] слишком маленьким, будем увеличивать, пока не станет [math]m \ge k[/math]. Тогда общее время алгоритма - [math] \sum_{t=0}^{O(\log\log k)} O\left(n \log(2^{2^t})\right) = O(n) \sum_{t=0}^{O(\log\log k)} O(2^t) = O\left(n \cdot 2^{1+O(\log\log k)}\right) = O(n \log k).[/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 для верхней и нижней половины.



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

Hull1.png

Очевидно, что выпуклая оболочка всего множества является объединением выпуклых оболочек для верхнего и нижнего множества. Докажем, что алгоритм верно строит оболочку для верхнего множества, для нижнего рассуждения аналогичны. Точки [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]

Ссылки