Geometry of BST

Get Started. It's Free
or sign up with your email address
Rocket clouds
Geometry of BST by Mind Map: Geometry of BST

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

7. Independent Rectangle Bounds

7.1. (1) Каждый треугольник не ASS (2) Нет строго вложения прямоугольников (3) Нет непустого нахлеста треугольников

7.2. X -- набор точек, I -- набор независимых прямоугольников в X. Minimal ASS (X) >= |X| + |I| / 2