Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)

Материал из Викиконспекты
Версия от 00:27, 16 января 2014; 194.85.161.2 (обсуждение) (Новая страница: «<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1p...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Эта статья находится в разработке!


Пусть дано изначально пустое множество [math]S[/math] и последовательность точек [math]\{s_i\}^n_{i = 1}[/math], которые последовательно добавляются или удаляются из [math]S[/math] (естественно, точка может быть удалена, если она уже принадлежит [math]S[/math]). Требуется на каждой итерации поддерживать выпуклую оболочку [math]S[/math].

В статье описан алгоритм, требующий [math]O(\log^2{n})[/math] времени на добавление/удаление точки.

Левые и правые выпуклые оболочки. Эффективная конкатенация двух левых оболочек

Определим левую (правую) выпуклую оболочку множества точек [math]P[/math], как выпуклую оболочку множества [math]P \cup \{\infty_+\} [/math] [math](P \cup \{\infty_-\})[/math], где [math]\infty_L = (-\infty, 0), \infty_R = (+\infty, 0)[/math]. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек.

Алгоритм

Источники