Изменения
Нет описания правки
Введем некоторые обозначения. Пусть <tex>Int(S)</tex> - множество всех точек пересечения отрезков из множества <tex>S</tex>, а <tex>K = |Int(S)|</tex> - количество таких пересечений ;<br>
Через <tex>\langle a, b \rangle</tex> обозначим вертикальную полосу, которая ограничена прямыми <tex>x = a</tex> и <tex>x = b</tex>, а через <tex>s</tex> {{---}} отрезок с концами абсцисс вершинами в точках с абсциссами <tex>l</tex> и <tex>r</tex>.<br>
Рассмотрим взаимное расположение вертикальной полосы <tex>\langle a, b \rangle</tex> и отрезка <tex>s</tex>.
{{Определение
|definition=
Будем говорить, что отрезок <tex>s</tex>, с концами абсцисс вершинами в точках с абсциссами <tex>l</tex> и <tex>r</tex> :
- '''содержит'''(span) полосу <tex>\langle a, b \rangle</tex>, если <tex>l \le a \le b \le r</tex>; <br>
- '''внутренний'''(inner) для полосы <tex>\langle a, b \rangle</tex>, если <tex>a < l < r < b</tex>; <br>
|statement=
Если лестница <tex>D</tex> полностью соотносима множеству отрезков <tex>S</tex>, где <tex>S</tex> состоит из отрезков, пересекающих полосу <tex>\langle a, b \rangle</tex>, тогда <tex>|S| \le Ends_{a, b}(S) + |Int(D, S)|</tex>,<br>
где <tex>Ends_{a, b}(S)</tex> это число концов вершин отрезков <tex>S</tex>, находящихся в пределах полосы <tex>\langle a, b \rangle</tex>.
}}
Учитывая [[#lemma1|лемму]], заключаем, что функция <tex>SearchInStrip_{a, b}(L, R)</tex> работает за <tex>O(|L| + |Int_{a, b}(L)|)</tex>.
Предположим, что все отрезки лежат в полосе <tex>\langle a, b \rangle</tex>. Таким образом в самом начале у нас есть пара <tex>(S, \langle a, b, \rangle)</tex>.
Что же дальше происходит: множество <tex>S</tex> ''распадается'' в подмножества <tex>Q</tex> и <tex>S'</tex>, после чего лестница <tex>D = (Q, \langle a, b \rangle)</tex> становится полностью соотносимой множеству <tex>S'</tex>. Необходимо найти пересечения отрезков из <tex>D</tex> и <tex>S'</tex>, затем, все пересечения в <tex>S'</tex>. Чтобы найти пересечения отрезков в <tex>S'</tex>, мы ''режем'' полосу <tex>\langle a, b \rangle</tex> и множество <tex>S'</tex> по вертикале <tex>x = c</tex> на полосы <tex>\langle a, с \rangle</tex>, <tex>\langle с, b \rangle</tex> и множества <tex>S'_{ls}</tex>, <tex>S'_{rs}</tex> соответственно, где c является медианой вершин отрезков, между <tex>a</tex> и <tex>b</tex>. Затем мы рекурсивно вызываем функцию к парам <tex>(S'_{ls}, \langle a, c \rangle)</tex> и <tex>(S'_{rs}, \langle c, b \rangle)</tex>. Ключевым является тот факт, что согласно [[#lemma1|лемме]] <tex>|S'| \le Ends_{a, b}(S') + |Int(D, S')|</tex>, таким образом, число дополнительных отрезков, появляющихся после ''разрезаний'' пропорционально числу найденных пересечений.
===Пункт подробностей =)===
Давайте разберемся с алгоритмом более подробнее:
Не умаляя общности, предположим, что все пересечения и вершины отрезков имеют разные абсциссы. В конечном счете, их можно будет ''поставить на свое место'' введением дополнительных свойств. Рассматриваем целые координаты на промежутке <tex>\[1, 2N\]</tex>.
Итак, пусть <tex>p_i{</tex>
So, let p,, i and s(i) be the ith endpoint its abscissa and the segment to which it belongs, respectively.
Основная задача нашего алгоритма, это рекурсивная функция <tex>TreeSearch</tex>. Мы соединяем каждый вызов функции с узлом некоего двоичного дерева, именуемого далее ''рекурсивным деревом''. Мы отмечаем все значения, множества и параметры вызова соответствующим узлом. As a result we shall analyze our algorithm examining the recursion tree. Let RT be the set of all nodes of recursion tree, and V be the set of internal nodes. We shall define some values, sets and notations inside the bodies of procedures.
procedure IntersectingPairs(SO ).
Sort the 2N endpoints by abscissa and
find p,, s(i), i= 1,,..,2N; ST := S.;
TreeSearch(S,, 1, 2N);
end procedure.
procedure TreeSearch(S., b, e).
Ife–b=l then
L. =sort S. by <b; SearchInStripb,. (LU, R.); exit;
endif
Split S. into Q. and S: so that staircase
Du := (Qv, (b, e)) be complete relative to S:;
Find lnt(DV , S:);
c:= L(b + e)/2J;
Place segments of S:
crossing the strip (b, c) into S[~(V ) and
the strip (c, e) into s~.(~);
TreeSearch(S1.(V), b, c);
TreeSearch(ST,(V), c, e);
end procedure.
==Примечания==
