Изменения

Предположим у нас есть запрос на локализацию точки <tex>q</tex>. Время , затраченное , на этот запрос будет линейно зависеть от глубина графа.

При добавлении в карту очередного отрезка(в дальнейшем , итерация алгоритма) , глубина графа увеличивается максимум на 3. Из этого мы можем сделать простую оценку.

Как говорилось раньше , отрезки мы добавляем рандомнов случайном порядке, а потому , редко будет самый ужасный случай и , с вероятностных точек зрения , время на запрос будет меньше.

Рассмотрим путь , пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за <tex>X_i</tex> - количество узлов , созданных на итерации <tex>i</tex>.

Так как никто не выбирал исходное множество отрезков и запрос <tex>q</tex>, <tex>X_i</tex> {{- --}} рандомная величина , зависящая только от рандомного порядка добавления отрезков.

Как уже упоминалось , на каждой итерации добавляется не более 3 узлов, а значит <tex>X_i\leq 3</tex> <= 3.

Считая, что <tex> P_i </tex> {{- --}} вероятность того, что существует узел, который встречается при нашем запросе , созданный на <tex>i</tex>-ой итерации.

Что значит, что узел был создан на <tex>i</tex>-ой итерации и встретился при запросе <tex>q</tex>?

Это значит, что на <tex>i - 1</tex>-ой итерации мы локализовывали <tex>q </tex> в трапецоиде <tex> \Delta_q(i - 1) </tex>, а на <tex>i</tex>-ой итерации уже в трапецоиде <tex> \Delta_q(i) </tex> и эти два трапецоида разные.

Таким образом <tex>P_i</tex> = P(<tex> \Delta_q(i) \ne \Delta_q(i - 1)) </tex>).

Если эти два трапеецоида не равны, значит на i-ой итерации трапецоид <tex> \Delta_q(i) </tex> был одним из созданных при модификации.

Заметим, что все трапецоиды , созданные на этой итерации , были смежны текущему отрезку(<tex> s_i </tex>).

Значит либо <tex> s_i </tex> = \operatorname{top(<tex>} \Delta_i</tex>) или bottom(<tex>\operatorname{bottom} \Delta_i</tex>), либо концы <tex>s_i</tex> = \operatorname{leftp(<tex>} \Delta_i</tex>) или rightp(<tex>\operatorname{rightp} \Delta_i</tex>).

Зафиксируем множество отрезков на <tex>i</tex>-ой итерации. Тогда состояние трапецоидов никак не будет зависеть от порядка добавленных отрезков.

Тогда, вероятность изменения трапецоида {{- --}} это его вероятность исчезнуть , если удалится <tex>s_i</tex>.

Тогда переходим, к top(<tex>\operatorname{top} \Delta_i</tex>) и т.п. так как мы уже говорили, что <tex>s_i</tex> будет определенной стороной при навигации.

Отрезки добавлялись рандомно , поэтому , в качестве <tex>s_i</tex> мог быть любой отрезок из <tex>S_i</tex>. А , тогда , вероятность для всех сторон 1<tex>\frac1i</itex>.

Таким образом <tex>P_i = P( \Delta_q(i) \ne \Delta_q(i - 1)) = P( \Delta_q(i) \in \Delta_q(i - 1) ) \le 4/i\frac4i</tex>

<tex>\sum^{n}_{i=1}E[X_i] \le \sum^{n}_{i=1}3P_i \le \sum^{n}_{i=1}\frac{12/}i \le 12\sum^{n}_{i=1}(1/i) \approx 12 \cdot log(n)</tex>

Заметим, что количество трапецоидов , как мы доказали раньше , равно <tex>\mathcal{O}(n)</tex>, поэтому мы должны оценить количество узлов созданых на <tex>i</tex>-ой итерации.

Mem = <tex>\mathrm{Mem} = \mathcal{O}(n) + \sum^{n}_{i=1}</tex>количество узлов созданное на <tex>i</tex>-ой итерации

Обозначив за <tex>k_i </tex> количество узлов , созданное на <tex>i</tex>-ой итерации

Mem = <tex>\mathrm{Mem} = \mathcal{O}(n) + \sum^{n}_{i=1}E[k_i]</tex>E[k_i]

Используя вывод из предыдущей части получаем, что <tex>E[k_i] \le \frac{\mathcal{O}(i)/}i = \mathcal{O}(1)</tex>

А тогда Mem = <tex>\mathrm{Mem} = \mathcal{O}(n)</tex>

Из этих двух выводов очевидно следует, что время построения карты равно <tex>\mathcal{O}(nlognn \log n)</tex>.