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