==Асимптотика==
===Запрос===
Запрос производится за время пропорцианальное глубине Предположим у нас есть запрос на локализацию точки q. Время затраченное на этот запрос будет линейно зависеть от глубина графа. При добавлении в карту очередного отрезка(поисковой структурыв дальнейшем итерация алгоритма). Если считать, что на каждой итерации глубина увеливается графа увеличивается максимум на 3. Из этого мы можем сделать простую оценку. Наибольшее время на запрос, то время работы которое мы можем потратить {{---}} 3n. Произойдет это в худшем случаи будет O(3n)самом ужасном из самых ужасных случаев. Но Как говорилось раньше отрезки мы вспоминаем, что порядок добавления отрезков рандомныйдобавляем рандомно, а потому наврядли всегда редко будет худший самый ужасный случайи с вероятностных точек зрения время на запрос будет меньше.
Рассмотрим путь пройденный точкой по графу. Каждый узел был создан на какой-то итерации цикла. Обозначим за <tex>X_i</tex> - количество узлов созданных на итерации i.
Эта Так как никто не выбирал исходное множество отрезков и запрос q, <tex>X_i</tex> - рандомная величина зависит зависящая только от рандомного порядка добаления добавления отрезков(если множество установлено).
Будет искать математическое ожидание глубины графа.<tex>E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i]</tex>
Как уже упоминалось на каждой итерации добавляется не более 3 узлов, а значит <tex>E[\sum^{n}_{i=1}X_i] = \sum^{n}_{i=1}E[X_i]</tex><= 3.
Считая, что <tex> P_i </tex> - вероятность того, что существует узел, который встречается при нашем запросе созданный на i-ой итерации был добавлен узел.
<tex>\sum^{n}_{i=1}E[X_i] <= \sum^{n}_{i=1}3P_i</tex>
Наша задача, понять чем ограничена P_i. Пусть Начинаем оценивать <tex> \Delta_q(i) P_i </tex> - трапецоид содержащий q . Что значит, что узел был создан на i-ой итерации.и встретился при запросе q? СкажемЭто значит, что произошло изменение на i- 1-ой итерации если мы локализовывали q в трапецоиде <tex> \Delta_q(i- 1) </tex> != , а на i-ой итерации уже в трапецоиде <tex> \Delta_q(i - 1) </tex>и эти два трапецоида разные. То есть, после добавления непонятно чего в карту, трапецоид изменился.
Таким образом P_i = 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> = top(<tex>\Delta_i</tex>) или bottom(<tex>\Delta_i</tex>), значит на i-ой итерации трапецоид либо концы <tex>s_i</tex> = leftp(<tex> \Delta_qDelta_i</tex>) или rightp(i) <tex>\Delta_i</tex> был одним из созданных при моификации).
Заметим, что все трапецоиды созданные Зафиксируем множество отрезков на этой i-ой итерации были смежны текущему отрезку. Тогда состояние трапецоидов никак не будет зависеть от порядка добавленных отрезков.
Либо этот отрезок был top или bottomТогда, либо вероятность изменения трапецоида - это его концы были leftp или rightp. Представим, что наш трапецоид вероятность исчезнуть если удалится <tex> \Delta_q(i) s_i</tex> исчез когда мы удалили текущий отрезок. Он мог исчезнуть только если исчез один из указателей(top, bottom ...).
Рассмотрим вероятность этого исчезновенияТогда переходим, к top(<tex>\Delta_i</tex>) и т.п. так как мы уже говорили, что <tex>s_i</tex> будет определенной стороной при навигации.
Так как отрезки мы добавляли Отрезки добавлялись рандомно поэтому в рандомном порядке, качестве <tex>s_i</tex> мог быть любой отрезок из <tex>S_i</tex>. А тогда вероятность текущему отрезку быть top или bottom равна для всех сторон 1/i.
leftp исчезает только в том случаи если leftp была концом теккущего отрезка. А потому эта вероятность тоже равна 1/i. Аналогично для rightpСуммируем по всем 4 сторонам.
Таким образом P_i = P(<tex> \Delta_q(i) \ne \Delta_q(i - 1) </tex>) = P(<tex> \Delta_q(i) \in \Delta_q(i - 1) </tex>) <= 4/i
<tex>\sum^{n}_{i=1}E[X_i]</tex> <= <tex>\sum^{n}_{i=1}3P_i <= \sum^{n}_{i=1}12/i <=12\sum^{n}_{i=1}(1/i) \approx 12*log(n)</tex>
Ура
===Память===
Заметим, что количество трапецоидов как мы доказали раньше равно O(n), поэтому мы должны оценить количество узлов созданых на i-ой итерации.
