Алгоритм Джарвиса(Метод заворачивания подарка)

Материал из Algocode wiki
Версия от 13:15, 26 февраля 2020; Глеб (обсуждение | вклад) (Новая страница: «Давайте выберем какую-то точку, которая гарантированно попадет в минимальную выпуклую о...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Давайте выберем какую-то точку, которая гарантированно попадет в минимальную выпуклую оболочкуо, например обычно берут нижнюю и если таких несколько, то самую левую из них. Теперь давайте по одной набирать точки, как бы заворачивая нашу выпуклую оболочку(отсюда и название). Как же нам найти следующую точку в выпуклую оболочку, давайте пройдемся по точкам, которые мы еще не взяли в МВО и среди них выберем с минимальным полярным углом.

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

Асимптотика : для каждой точки выпуклой оболочки мы из всех оставшихся точек будем искать оптимальную - что будет работать за h(размер выпуклой оболочки) $\cdot n$

Важно помнить, что именно $O(hn)$, а не $O(n^2)$, так как существуют задачи на это.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin