170
правок
Изменения
Нет описания правки
Если на правой стороне есть точка, то сейчас мы бы обращались к ней, а не к <tex>y</tex>.
Если на верхней стороне есть точка <tex>z</tex> с ключом меньше <tex>y</tex>, мы будем обращаться к ней тогда же, когда и к <tex>уy</tex>, значит мы может перейти к прямоугольнику, построенному на точках <tex>x</tex> и <tex>z</tex>.
Когда таких точек (как <tex>z</tex>) не останется, то мы получим прямоугольник, у которого нет точек на всех сторонах, а это противоречит исходному условию.
Поэтому при перестроении декартова дерева нам не потребуется переходить из нашей верхней зоны.
}}
Таким образом, мы получили какую-то offline оптимальность.
Получим нижнюю оценку на оптимум.
<tex>Оптимум OPT = омегаomega(f) </tex>
Если что-то работает за <tex>O(f * g)</tex>, значит это работает не более, чем в <tex>g</tex> раз хуже.
Покроем их независимыми прямоугольниками.
Прямоугольники независимы, если угол одного не лежит внутри другого.
Можно показать, что <tex>оптимум(OPT) >= M</tex>(число запросов) + максимальное число независимых прямоугольников * 1/2</tex>
==Вторая нижняя оценка Уилберра (Wilber) ==
Рассмотрим запрос <tex>х</tex>
Пусть левая граница <tex>= -бесконечностьinf</tex>, правая граница <tex>= +бесконечностьinf</tex>
Идем от ключа <tex>x</tex> назад и ищем, когда в предыдущий раз мы обращались к этому ключу.
И каждый раз, когда встречается значение больше, чем наше, но меньше правой границы, мы сдвигаем правую границу.
Аналогично с левой границей.
Когда-то рано или поздно наши границы встретятся в <tex>хx</tex>
Можно показать, что из этой оценки выходит следующая оценка
Напишем <tex>r</tex>, если меняется правая граница и <tex>l</tex> - если левая.
Назовем <tex>ch(i)</tex> количество смен <tex>r</tex> на <tex>l</tex> и обратно
<tex>Оптимум OPT >= сумме по всем запросам(\sum\limits_{i) (\in [1, n]} 1 + ch(i))</tex>
Док-во упр
