74
правки
Изменения
→Левая и правая выпуклые оболочки
== Левая и правая выпуклые оболочки ==
Определим левую (правую) выпуклую оболочку множества точек <tex>P</tex>, как выпуклую оболочку множества <tex>P \cup \{\infty_+\}</tex> <tex>(P \cup \{\infty_-\})</tex>, где <tex>\infty_- = (-\infty, 0), \infty_+ = (+\infty, 0)</tex>. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек. Далее будем рассматривать только динамическое поддержание левой оболочки (далее, для краткости, будем называть её просто выпуклой оболочкой). Заметим также, что точки вдоль выпуклой оболочки отсортированы по ординате.
[[Файл:Lc_rc.png|400px|thumb|center|Левая и правая выпуклые оболочки некоторого множества точек]]
[[Файл:Bridge_hull.png|400px|thumb|center|Мост между двумя выпуклыми оболочками, разделенными горизонтальной прямой]]
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Case_a.png|thumb|300px|center|a. Касательная найдена]]
|[[Файл: Case_b.png|thumb|300px|center|b. Может быть отброшена часть C после q, а также часть A перед p]]
|[[Файл: Case_c.png|thumb|300px|center|c. Может быть отброшена часть C перед q, а также часть A перед p]]
|
|}
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Case_d.png|thumb|300px|center|d. По аналогии со случаем b]]
|[[Файл: Case_e.png|thumb|300px|center|e. По аналогии со случаем c]]
|[[Файл: Case_f.png|thumb|300px|center|f. Может быть отброшена часть C после q, а также часть A перед p]]
|
|}
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Case_g.png|thumb|300px|center|g. Только часть C после q может быть отброшена]]
|[[Файл: Case_h.png|thumb|300px|center|h. По аналогии со случаем h]]
|[[Файл: Case_i.png|thumb|300px|center|i. В этом случае нельзя сразу сказать, какие части A и C могут быть отброшены. Случай дробится на два]]
|
|}
== Структура данных ==
