234
правки
Изменения
→Корректность
== Корректность ==
Докажем, что на каждом шаге множество <tex>p_i</tex>-тых является выпуклой оболочкой всех уже рассмотренных точек. Доказательство проведем по индукции.
1)База. Для трех первых точек утверждение, очевидно, выполняется.
2)Переход. Предположим от противногоПусть для <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> точек совпадают.
== Псевдокод ==
