Изменения

Перейти к: навигация, поиск
Левая и правая выпуклые оболочки
Определим левую (правую) выпуклую оболочку множества точек <tex>P</tex>, как выпуклую оболочку множества <tex>P \cup \{\infty_+\}</tex> <tex>(P \cup \{\infty_-\})</tex>, где <tex>\infty_- = (-\infty, 0), \infty_+ = (+\infty, 0)</tex>. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек. Далее будем рассматривать только динамическое поддержание левой оболочки (далее, для краткости, будем называть её просто выпуклой оболочкой). Заметим также, что точки вдоль выпуклой оболочки отсортированы по ординате.
{|border="0" cellpadding="5" width=30% align=center|[[Файл:Lc_rc.png|400px|thumb|center|Левая и правая выпуклые оболочки некоторого множества точек]]|[[Файл:Bridge_hull.png|400px|thumb|center|Мост B между двумя выпуклыми оболочками, разделенными горизонтальной прямой]]||}
[[Файл:Bridge_hullПусть множество точек <tex>P</tex> разбито горизонтальной прямой на два множества <tex>A</tex> и <tex>C</tex>.png|400px|thumb|center|Мост Рассмотрим выпуклые оболочки <tex>A</tex> и <tex>C</tex>. Будем называть мостом (bridge) отрезок общей касательной к этим оболочкам, заключённый между двумя выпуклыми оболочкамиточками касания. Тогда выпуклая оболочка ко всему множеству <tex>P</tex> естественным образом получается объединением частей оболочек <tex>A</tex> и <tex>C</tex>, и моста <tex>B</tex>. Основная идея алгоритма заключается в эффективном (за <tex>O(\log{n})</tex>) отыскании моста, разделенными горизонтальной прямой]]соединяющего две такие оболочки.
{|border="0" cellpadding="5" width=30% align=center
73
правки

Навигация