234
правки
Изменения
→Алгоритм QuickHull
= Алгоритм Чена =
= Алгоритм 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>.]]
1)Найдем самую левую нижнюю точку <tex>p_0</tex> и самую правую нижнюю точку <tex>p_1</tex>.
2)Возьмем все точки выше прямой <tex>p_0 p_1</tex>.
3)Найдем среди этого множества точку <tex>p_i</tex>, наиболее отдаленную от прямой (если таких несколько, взять самую правую).
4)Рекурсивно повторить шаги 2-3 для прямых <tex>p_0 p_i</tex> и <tex>p_i p_1</tex>, пока есть точки.
5)Добавить в ответ точки <tex>p_0 .. p_i .. p_1</tex>, полученные в п. 3.
6)Повторить пункты 2-5 для <tex>p_1 p_0</tex> (то есть для "нижней" половины).
7)Ответ - объединение списков из п. 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>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/QuickHull Английская статья — Wikipedia]
