Асимптотически оптимальный алгоритм перечисления пересечений ребер двудольного графа

Поставленные задачи относятся к классу задач о вычислении множественных геометрических пересечений, возникающих в таких приложениях, как анализ больших интегральных схем, машинная графика и др. Предложены алгоритмы их решения с оценками, пропорциональными $N\lg N+K$ и $N\lg N$ соответственно, для задачи перечисления и задачи подсчета числа точек пересечения ребер специального двудольного графа, расположенного на плоскости. Здесь $N$ - число ребер, $K$ - число точек пересечения. Доказана асимптотическая оптимальность предложенных алгоритмов.