234
правки
Изменения
→Алгоритм Грэхема
== Корректность ==
{{notready}}
Докажем, что на каждом шаге множество <tex>p_i</tex>-тых является выпуклой оболочкой всех уже рассмотренных точек. Доказательство проведем по индукции.
1)База. Для трех первых точек утверждение, очевидно, выполняется.
2)Переход. Предположим от противного, что утверждение на <tex>i</tex>-м шаге перестает выполняться. Тогда существует два варианта:
* В нашей оболочке есть лишние точки.
Этого не может быть, так как на каждом шаге мы добавляем ровно одну точку, которая точно входит в оболочку, так как имеет наибольший полярный угол среди всех остальных.
* В нашей оболочке нет каких-то точек, которые есть в настоящей.
Удаляем мы только те
== Псевдокод ==
Inplace-реализация алгоритма. <tex>S[1..n]</tex> - исходное множество, <tex>n > 2</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 k-- swap(S[p], S[k + 1]) return k
== Сложность ==
Сортировка точек занимает <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]
= Алгоритм =
