1. BST Model
1.1. Унитарные операции: переход и поворот
1.2. Стоимость доступа
1.2.1. Если один запрос, то O(log n)
1.2.2. Если много запросов, то непонятно
2. BST Execution
2.1. Sequential Access Property
2.1.1. 1, 2, 3, 4, ... => O(1)/op (amortized)
2.1.2. Splay Tree обладает этим свойством
2.2. Dynamic Finger Property
2.2.1. |x_{i} - x_{i+1}| = k => O(\log k)/op
2.2.2. Splay Tree обладает этим свойством
2.3. Entropy Bound / Static Optimality
2.3.1. x_i ~ p_i => O(H(p))/op
2.3.2. Лучшее, что можно без вращений
2.3.3. Splay Tree обладает этим свойством
2.4. Working-Set Property
2.4.1. Между последовательными доступами к x_i находится t_i разных элементов => O(\log t_i)
2.4.2. Если запросы только к подмножеству S => O(\log |S|)
2.4.3. Splay Tree обладает этим свойством
2.5. Unified Property
2.5.1. t_{ij} разных ключей между x_i и x_j
2.5.2. x_j стоит O(\min_i [ t_{ij} + |x_i - x_j| + 2 ])
2.5.3. "Fast, if close to something recent."
2.5.4. 1, n / 2, 2, n / 2 + 1, ... => O(1)/op (amortized)
2.5.5. Можно на pointer machine
2.5.6. Можно на BST с аддитивным O(\log \log n)
2.5.7. OPEN: Можно ли на BST?
2.5.8. CONJ: Splay Tree?
2.6. Dynamic Optimality
2.6.1. Реализует OPT по всем возможным исполнениям E
2.6.2. Tango Trees -- O(log log n * OPT)
2.6.3. OPEN: Можно ли на BST?
2.6.4. OPEN: Можно ли посчитать OPT? Или O(1)-аппроксимировать?
2.6.5. CONJ: Splay Tree?
3. BST Model (Формально)
3.1. tau -> tau' -- Реконфигурация (стоимостью |tau|) поддеревьев в дереве R, содержащих корень дерева и построенных на одном и том же множестве ключей, реализуемая заменой tau на tau'
3.2. E = (tau_1, tau_1 -> tau'_1, tau_2, tau_2 -> tau'_2, ...) -- Исполнение S (стоимостью суммарной по tau), если все реконфигурации валидны, и s_i \in tau_i
3.3. Эквивалентно модели с переходами и поворотами, потому что структуру дерева можно перестроить за линию
4. Independent Rectangle Bounds
4.1. (1) Каждый треугольник не ASS (2) Нет строго вложения прямоугольников (3) Нет непустого нахлеста треугольников
4.2. X -- набор точек, I -- набор независимых прямоугольников в X. Minimal ASS (X) >= |X| + |I| / 2
5. Arbor(e)ally Satisfied Set
5.1. Определение
5.1.1. Две точки AS по отношению к P, если они ортоколлинеарны, или если есть третья точка и P, лежащая в прямоугольнике
5.1.2. P -- ASS, если все пары точек AS
5.1.3. arboreal ~ treelike
5.2. Это примерно сетка
5.2.1. Для любых двух точек из P найдутся точки, которые лежат на прямоугольнике и инцидетны a и b
5.2.2. Доказывается по индукции
5.3. Эквивалентность E и ASS
5.3.1. (E => ASS) От противного; пусть есть (a, i), (b, j), i < j и точек между a и b во время [i; j] не затрагивается. c = lca_i (a, b). Рассмотреть случаи c = a и c = b.
5.3.2. (ASS => E) Определить Next(x, i). Построить дучу на N(x, i). tau_i -- дуча из элементов N(x, i) для фиксированного i. Показать, что свойства дучи сохраняются.
5.4. O(1)-эквивалентность Online-E и Online-ASS
5.4.1. Без знания будущего
5.4.2. Структура примерно восстанавливается по general treap на previous access times
5.4.3. В узлах general treap живут split-деревья
5.5. Следствия
5.5.1. OPT не зависит от замены x на зеркальный (n - x)
5.5.2. OPT не зависит от разворота времени
5.5.3. OPT не зависит от swap-а временной и пространственной составляющей
5.6. Оффлайн-постановка
5.6.1. - Набор точек S выдается полностью - P = ASS (S)
5.7. Онлайн-постановка
5.7.1. - На i-ом шаге появляется точка (s_i, i) - Нужно выдать набор точек P_i так, что P_{<= i} -- ASS
6. Нижние оценки
6.1. Wibler's First Bound
6.1.1. Пусть L = (\el_1, ..., \el_k) -- вертикальные линии. X -- отсортировано по возрастанию y.
6.1.2. Рассмотрим \el_i, просматриваем точки по возрастанию y. На каждую перемену знака x_j относительно \el_i добавляем независимый прямоугольник.
6.1.3. Рекурсивно строим набор cлева и справа.
6.1.4. L = (n / 2, n / 4, 3 n / 4, n / 8, 3 n / 8, 5 n / 8, 7 n / 8, ... )
6.2. Wibler's Second Bound
6.2.1. Смотрим на p \in X в порядке увеличения y.
6.2.2. Берем те ортогонально видимые пары точек, которые меняют сторону относительно абсциссы p.
6.2.3. CONJ: Wibler 2 = O(OPT)
7. Greedy Future
7.1. С точки зрения деревьев
7.1.1. На текущем пути поиска tau_i сделать корнем s_{i+1} (или предшественника, а правым сыном -- потомка; или аналогично)
7.1.2. Рекурсивно выстроить левые и правые поддеревья для s_{i+j}
7.2. С точки зрения ASS
7.2.1. На i-ой sweep line достроить точек до минимально допустимого ASS на точках X = { (x, y) | y <= i }
7.2.2. Внезапно, online-алгоритм!
7.3. CONJ (W): Greedy = O(OPT)
7.4. CONJ (S): Greedy = OPT + O(m)
7.5. Доказанные оценки
7.5.1. O(log n)-оптимальность
7.5.2. Sequential Access Property
7.5.3. Static Optimality
7.5.4. Working-Set Property
7.5.5. [1] arXiv:1102.4523, Goyal, Gupta; 2011
7.5.6. [2] arXiv:1102.4884, Fox; 2011