Изменения

Давайте разберемся с алгоритмом более подробнееподробно:

Не умаляя общности, предположим, что все пересечения и вершины отрезков имеют разные абсциссы. В (в конечном счете, их можно будет ''поставить на свое место'' отсортировать введением дополнительных свойств). Рассматриваем Будем рассматривать целые координаты на промежутке <tex>\[1, 2N\]</tex>. Пусть <tex>p_i{</tex> и <tex>s(i)</tex> будут координатами вершин <tex>i</tex>-того отрезка.(???)

ИтакОсновная задача нашего алгоритма, пусть это рекурсивная функция <tex>p_i{TreeSearch</tex>So. Мы соединяем каждый вызов функции с узлом некоего двоичного дерева (далее ''рекурсивное дерево''). Мы отмечаем все значения, let pмножества и параметры вызова соответствующим узлом. В результате,мы проанализируем наш алгоритм рекурсивного дерева. Обозначим множество всех вершин рекурсивного дерева за <tex>RT</tex>, i and sа множество внутренних вершин за <tex>V</tex>. (iWAT??) be the ith endpoint its abscissa and the segment to which it belongs, respectively.

Основная задача нашего алгоритма <tex>IntersectingPairs(S_v, это рекурсивная функция a, b):</tex> Отсортировать <tex>TreeSearch2*N</tex>. Мы соединяем каждый вызов функции с узлом некоего двоичного деревавершин по координатам и найти <tex>p_i, s(i), i = 1, именуемого далее ''рекурсивным деревом''. Мы отмечаем все значения, множества и параметры вызова соответствующим узлом. 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 values2*N; S_r \leftarrow S_0</tex> <tex>TreeSearch(S_r, 1, sets and notations inside the bodies of procedures.2*N)</tex>;

procedure IntersectingPairs <tex>TreeSearch(SO ).Sort the 2N endpoints by abscissa andfind pS_r,a, s(ib), i= 1,,..,2N; ST := S.;</tex>TreeSearch(S,, 1, 2N);end procedure.procedure TreeSearch(S., '''if''' <tex>b, e).Ife–b- a =l 1</tex> '''then''' <tex>\{</tex> <tex>L. =\leftarrow sort S. S_v by <b_b</tex>; SearchInStripb <tex>SearchInStrip_{a,. b}(LUL_v, R.R_v)</tex>; exit break;endif <tex>\}</tex>