Изменения
→Ключевые моменты
Давайте разберемся с алгоритмом более подробно:
Не умаляя общности, предположим, что все пересечения и вершины отрезков имеют разные абсциссы (в конечном счете, их можно будет отсортировать введением дополнительных свойств). Будем рассматривать целые координаты на промежутке <tex>[1, 2N]</tex>. Пусть Обозначим через <tex>p_i</tex> и слева направо конец отрезка множества <tex>s(i)S_0</tex> будут координатами вершин , а через <tex>s(i)</tex>-того отрезкаотрезок, которому он принадлежит соответственно.
Основная задача нашего алгоритма, это рекурсивная функция <tex>TreeSearch</tex>. Соединим каждый вызов функции с узлом некоего двоичного дерева (далее ''рекурсивное дерево''). Соответствующим узлом отметим все значения, множества и параметры вызова. Обозначим множество внутренних вершин за <tex>V</tex>.
