74
правки
Изменения
→Левая и правая выпуклые оболочки
Определим левую (правую) выпуклую оболочку множества точек <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 между двумя выпуклыми оболочками, разделенными горизонтальной прямой]]||}
{|border="0" cellpadding="5" width=30% align=center
