Бонусная лекция. Корневая и Диаграмма Вороного (20 марта 2014)

1. Корневая эвристика со split и rebuild
1. Split: разбить кусок, содержащий i-ю позицию на 2 куска. [code]
2. Insert(i, x), Delete(i), количество кусков увеличивается на 2, когда станет слишком много, делаем rebuild
3. Reverse [L..R], getMin [L..R], relaxMax [L..R] [code]
2. Диаграмма Вороного
1. Определение. Хранение (ориентированный граф, для каждого ребра есть ссылка на обратное и номер грани)
2. Доказательство линейности размера
3. Построение за O(n²)
4. В теории можно строить за O(nlogn). Решение задача "ближайшая точка для каждой" за O(n) при построенной диаграмме.
3. Ближайшие точки
1. Поиск ближайшей точки в A для каждой точки множества A за O(n√ n ), где n = |A|