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

Материал из Algocode wiki
Версия от 20:27, 29 февраля 2020; Глеб (обсуждение | вклад) (Новая страница: «Научимся искать выпуклую оболочку за $O(n\log(h))$, где $h$ - размер выпуклой оболочки Разобьем...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Научимся искать выпуклую оболочку за $O(n\log(h))$, где $h$ - размер выпуклой оболочки

Разобьем все точки на множества из $m$ точек($m$ - какое-то число, о котором мы поговорим позже).

На каждом таком множестве построим выпуклую оболочку алгоритмом Грэхема или Эндрю за $m\log{m}$, то есть суммарно для всех точек $n\log{m}$.

Затем будем проделывать алгоритм Джарвис следующим образом :

Выберем точку, которая точно будет в выпуклой оболочке(например самую нижнюю из левых), теперь будем искать точку с наименьшим полярным углом внутри каждой выпуклой оболочки, так как такую точку можно искать внутри выпуклого многоугольника тернарным поиском, то это будет работать за $O(h \cdot \frac{n}{m} \cdot log(m))$, следовательно суммарно наше решение работает за $O(n\log{m} + h \cdot \frac{n}{m} \cdot log(m))$, следовательно нам нужно взять $m$ примерно равным $h$.

Так как мы не знаем размера выпуклой оболочки в большинстве задач, то нам нужно как-то его подобрать, давайте тогда перебирать $t$, такое что $m = 2^{2^{t}}$, а затем брать в выпуклую оболочку во время алгоритма Джарвиса не более $m$ точек и проверять достаточно ли $m$ точек в выпуклой оболочке. Можно показать, что это работает за $O(n\log(h))$, так как $\sum\limits_{t = 1}^{2^{2^t} < h}{n\log{2^{2^t}}} = \sum\limits_{t = 1}^{2^{2^t} < h}{n \cdot 2^t}= O(n\log(h))$



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

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