Geometry of BST
создатель Ivan Pouzyrevsky
1. Arbor(e)ally Satisfied Set
1.1. Определение
1.1.1. Две точки AS по отношению к P, если они ортоколлинеарны, или если есть третья точка и P, лежащая в прямоугольнике
1.1.2. P -- ASS, если все пары точек AS
1.1.3. arboreal ~ treelike
1.2. Это примерно сетка
1.2.1. Для любых двух точек из P найдутся точки, которые лежат на прямоугольнике и инцидетны a и b
1.2.2. Доказывается по индукции
1.3. Эквивалентность E и ASS
1.3.1. (E => ASS) От противного; пусть есть (a, i), (b, j), i < j и точек между a и b во время [i; j] не затрагивается. c = lca_i (a, b). Рассмотреть случаи c = a и c = b.
1.3.2. (ASS => E) Определить Next(x, i). Построить дучу на N(x, i). tau_i -- дуча из элементов N(x, i) для фиксированного i. Показать, что свойства дучи сохраняются.
1.4. O(1)-эквивалентность Online-E и Online-ASS
1.4.1. Без знания будущего
1.4.2. Структура примерно восстанавливается по general treap на previous access times
1.4.3. В узлах general treap живут split-деревья
1.5. Следствия
1.5.1. OPT не зависит от замены x на зеркальный (n - x)
1.5.2. OPT не зависит от разворота времени
1.5.3. OPT не зависит от swap-а временной и пространственной составляющей
1.6. Оффлайн-постановка
1.6.1. - Набор точек S выдается полностью - P = ASS (S)
1.7. Онлайн-постановка
1.7.1. - На i-ом шаге появляется точка (s_i, i) - Нужно выдать набор точек P_i так, что P_{<= i} -- ASS
2. Нижние оценки
2.1. Wibler's First Bound
2.1.1. Пусть L = (\el_1, ..., \el_k) -- вертикальные линии. X -- отсортировано по возрастанию y.
2.1.2. Рассмотрим \el_i, просматриваем точки по возрастанию y. На каждую перемену знака x_j относительно \el_i добавляем независимый прямоугольник.
2.1.3. Рекурсивно строим набор cлева и справа.
2.1.4. L = (n / 2, n / 4, 3 n / 4, n / 8, 3 n / 8, 5 n / 8, 7 n / 8, ... )
2.2. Wibler's Second Bound
2.2.1. Смотрим на p \in X в порядке увеличения y.
2.2.2. Берем те ортогонально видимые пары точек, которые меняют сторону относительно абсциссы p.
2.2.3. CONJ: Wibler 2 = O(OPT)
3. BST Model
3.1. Унитарные операции: переход и поворот
3.2. Стоимость доступа
3.2.1. Если один запрос, то O(log n)
3.2.2. Если много запросов, то непонятно
4. BST Execution
4.1. Sequential Access Property
4.1.1. 1, 2, 3, 4, ... => O(1)/op (amortized)
4.1.2. Splay Tree обладает этим свойством
4.2. Dynamic Finger Property
4.2.1. |x_{i} - x_{i+1}| = k => O(\log k)/op
4.2.2. Splay Tree обладает этим свойством
4.3. Entropy Bound / Static Optimality
4.3.1. x_i ~ p_i => O(H(p))/op
4.3.2. Лучшее, что можно без вращений
4.3.3. Splay Tree обладает этим свойством
4.4. Working-Set Property
4.4.1. Между последовательными доступами к x_i находится t_i разных элементов => O(\log t_i)
4.4.2. Если запросы только к подмножеству S => O(\log |S|)
4.4.3. Splay Tree обладает этим свойством
4.5. Unified Property
4.5.1. t_{ij} разных ключей между x_i и x_j
4.5.2. x_j стоит O(\min_i [ t_{ij} + |x_i - x_j| + 2 ])
4.5.3. "Fast, if close to something recent."
4.5.4. 1, n / 2, 2, n / 2 + 1, ... => O(1)/op (amortized)
4.5.5. Можно на pointer machine
4.5.6. Можно на BST с аддитивным O(\log \log n)
4.5.7. OPEN: Можно ли на BST?
4.5.8. CONJ: Splay Tree?
4.6. Dynamic Optimality
4.6.1. Реализует OPT по всем возможным исполнениям E
4.6.2. Tango Trees -- O(log log n * OPT)
4.6.3. OPEN: Можно ли на BST?
4.6.4. OPEN: Можно ли посчитать OPT? Или O(1)-аппроксимировать?
4.6.5. CONJ: Splay Tree?
5. BST Model (Формально)
5.1. tau -> tau' -- Реконфигурация (стоимостью |tau|) поддеревьев в дереве R, содержащих корень дерева и построенных на одном и том же множестве ключей, реализуемая заменой tau на tau'
5.2. E = (tau_1, tau_1 -> tau'_1, tau_2, tau_2 -> tau'_2, ...) -- Исполнение S (стоимостью суммарной по tau), если все реконфигурации валидны, и s_i \in tau_i
5.3. Эквивалентно модели с переходами и поворотами, потому что структуру дерева можно перестроить за линию
6. Greedy Future
6.1. С точки зрения деревьев
6.1.1. На текущем пути поиска tau_i сделать корнем s_{i+1} (или предшественника, а правым сыном -- потомка; или аналогично)
6.1.2. Рекурсивно выстроить левые и правые поддеревья для s_{i+j}
6.2. С точки зрения ASS
6.2.1. На i-ой sweep line достроить точек до минимально допустимого ASS на точках X = { (x, y) | y <= i }
6.2.2. Внезапно, online-алгоритм!
6.3. CONJ (W): Greedy = O(OPT)
6.4. CONJ (S): Greedy = OPT + O(m)
6.5. Доказанные оценки
6.5.1. O(log n)-оптимальность
6.5.2. Sequential Access Property
6.5.3. Static Optimality
6.5.4. Working-Set Property
6.5.5. [1] arXiv:1102.4523, Goyal, Gupta; 2011
6.5.6. [2] arXiv:1102.4884, Fox; 2011