Изменения
Новая страница: «<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1p...»
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>
Пусть дано изначально пустое множество <tex>S</tex> и последовательность точек <tex>\{s_i\}^n_{i = 1}</tex>, которые последовательно добавляются или удаляются из <tex>S</tex> (естественно, точка может быть удалена, если она уже принадлежит <tex>S</tex>). Требуется на каждой итерации поддерживать выпуклую оболочку <tex>S</tex>.
В статье описан алгоритм, требующий <tex>O(\log^2{n})</tex> времени на добавление/удаление точки.
== Левые и правые выпуклые оболочки. Эффективная конкатенация двух левых оболочек ==
Определим левую (правую) выпуклую оболочку множества точек <tex>P</tex>, как выпуклую оболочку множества <tex>P \cup \{\infty_+\} </tex> <tex>(P \cup \{\infty_-\})</tex>, где <tex>\infty_L = (-\infty, 0), \infty_R = (+\infty, 0)</tex>. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек.
== Алгоритм ==
== Источники ==
<includeonly>[[Категория: В разработке]]</includeonly>
Пусть дано изначально пустое множество <tex>S</tex> и последовательность точек <tex>\{s_i\}^n_{i = 1}</tex>, которые последовательно добавляются или удаляются из <tex>S</tex> (естественно, точка может быть удалена, если она уже принадлежит <tex>S</tex>). Требуется на каждой итерации поддерживать выпуклую оболочку <tex>S</tex>.
В статье описан алгоритм, требующий <tex>O(\log^2{n})</tex> времени на добавление/удаление точки.
== Левые и правые выпуклые оболочки. Эффективная конкатенация двух левых оболочек ==
Определим левую (правую) выпуклую оболочку множества точек <tex>P</tex>, как выпуклую оболочку множества <tex>P \cup \{\infty_+\} </tex> <tex>(P \cup \{\infty_-\})</tex>, где <tex>\infty_L = (-\infty, 0), \infty_R = (+\infty, 0)</tex>. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек.
== Алгоритм ==
== Источники ==
