35.5 Исполнение алгоритма Any-Segment-Intersect. Положения движущейся прямой в критических точках показаны пунктиром; рядом выписаны пересекаемые отрезки (в порядке сверху - вниз) в момент сразу после прохода критической точки, Пересечение отрезков dub обнаруживается после удаления отрезка с.

через его правый конец.

Состояние дел у прямой можно хранить как упорядоченное множество отрезков, с которым выполняются следующие операции:

Insert (Г, s) : добавить отрезок s в Г;

Delete (Г, s) : удалить отрезок s из Г;

Above (Г, s) : указать отрезок, располагающийся непосредственно выше s в множестве Г;

Below (Г, s) : возвращает отрезок, располагающийся непосредственно ниже s в множестве Т.

(Говоря об отношении порядка в Г, мы описываем слова «выше» и «ниже» в соответствии с геометрическим смыслом этого отношения.)

Мы можем хранить (линейно) упорядоченное множество из п отрезков и выполнять любую из указанных операций за время О (lg п), используя красно-чёрное дерево, Заметим, что операции сравнения (какой из отрезков выше в данный момент) можно выполнить за время 0(1), используя векторные произведения (см. упр. 35.2-2).

Проверка пересечений

Построим алгоритм, который по заданному множеству S, состоящему из п отрезков, проверяет, есть ли среди них хотя бы два пересекающихся. Этот алгоритм использует красно-чёрное дерево для хранения текущего состояния дел у движущейся прямой.

Any-Segment-Intersect(S)

1Т \gets \emptyset

2сортируем концы отрезков в порядке возрастания абсцисс (точки

с равными абсциссами идут в порядке возрастания ординат); проверяем, нет ли совпадающих точек среди концов (если есть -возвращаем true)

3\emph{for} (для) каждой точки $р$ из полученного списка

4\emph{do} if $р$ --- левый конец некоторого отрезка $s$

5\emph{then} Insert (Т, s )

6\emph{if} (Above (T, s) существует и пересекает s)

(Below (T, s) существует и пересекает s)

7\emph{then return} true

8\emph{if} $p$ правый конец некоторого отрезка $s$

9\emph{then if} определены Above (T, s) и Below

и (Above (T, s) пересекает

10\emph{then return} true

11Deleted, s)

12 \emph{return} false

На рис. 35.5 показано выполнение алгоритма. Изначально множество Г пусто (строка 1). В строке 2 строится расписание ожидаемых событий, соответствующих концам отрезков (вообще-то критическими точками являются также моменты пересечения отрезков, но после обнаружения такого пересечения алгоритм заканчивает работу сразу же, так что эти моменты мы смело можем игнорировать.

Каждая итерация цикла for в строках 3-11 обрабатывает одну критическую точку. Если она соответствуют левому концу некоторого отрезка s, то в строке 5 этот отрезок добавляется в упорядоченное множество, а в строках 6-7 проверяется, не пересекается ли он часом с одним из соседних отрезков (если да, то алгоритм кончает работу и даёт ответ true). (Возможно, что критическая точка соответствует концам нескольких отрезков - в этом случае они добавляются один за другим.)

Если обрабатываемая критическая точка является правым концом некоторого отрезка s, то этот отрезок удаляется из Г (строка 11); предварительно проверяется, не пересекаются ли отрезки, которые разделял удаляемый отрезок и которые теперь становятся соседними (строки 9-10)

Так делается для всех концов всех отрезков; если при этом пересечение так и обнаруживается, то алгоритм возвращает false (строка 12).

Правильность алгоритма

Теорема 35.1

Процедура Any-Segment-Intersect(S) возвращает true в том и только том случае, когда среди отрезков множества S есть пересекающиеся.

Доказательство.

Заметим, что значение true возвращается лишь после того, как обнаружены два пересекающихся отрезка. Поэтому надо лишь проверить, что если в S есть пара пересекающихся отрезков, то она будет обнаружена.

Предположим теперь, что алгоритм не возвращает значения true, а просматривает по очереди все концы отрезков, не находит пересечения и возвращает значение false. Покажем, что в таком случае отрезки не пересекаются.

Рассмотрим сначала случай, когда концы всех отрезков имеют различные абсциссы. Тогда на каждой итерации цикла рассматривается новое значение абсциссы. Докажем, что при этом остаются верными такие свойства:

(a)множество Г соответствует положению прямой непосредственно справа от последней обработанной абсциссы;

(b)соседние в множестве Г отрезки не пересекаются.

Вначале эти свойства выполнены (Г пусто, движущаяся прямая не пересекает ни одного из отрезков, находясь слева от всех них). Проверим, что они остаются выполненными после прохода через один из концов (другими словами, после очередной итерации цикла).

Если очередная точка есть левый конец отрезка, то появляется новая точка пересечения с движущейся прямой. Начинающийся в ней отрезок не пересекается с соседними (в смысле текущего состояния множества Г) отрезками, иначе это было бы обнаружено. Остальные пары соседних отрезков были соседними раньше, так что мы уже знаем, что они не пересекаются.

Раз соседние отрезки не пересекаются, то на участке до следующего значения абсциссы в списке относительный порядок сохраняется (точка пересечения может быть только у несоседних отрезков и только после конца того отрезка, который их разделял).

Пусть теперь очередная точка есть правый конец отрезка. Тогда из множества Г удаляется элемент (как и полагается, если мы хотим, чтобы Г соответствовало положению прямой справа от очередной точки). Появляется новая пара соседних отрезков - про которую алгоритм проверяет, что они не пересекаются. По тем же причинам, что и раньше, можно утверждать, что до следующего значения абсциссы относительный порядок сохраняется.

Итак, свойства (а) и (Ь) проверены, и заодно доказано, что никакие два отрезка не пересекаются. В самом деле, раз между рассматриваемыми абсциссами порядок сохраняется, между ними пересечение невозможно; а при прохождении движущейся прямой через конец отрезка пересечение также невозможно, так как некоторые пересекающиеся отрезки были бы соседними слева или справа от прямой.

Осталось разобраться, почему наше рассуждение применимо к случаю, когда несколько концов отрезков лежат на одной вертикали (но не совпадают - это проверяется при сортировке концов отрезков). Это можно объяснить так: представим себе, что движущаяся прямая чуть-чуть наклонена влево (против часовой стрелки). Тогда она будет пересекать концы отрезков в разные (хотя, возможно, очень близкие) моменты времени, и просматриваться они будут как раз в нужном порядке (точки с одинаковой абсциссой - в порядке возрастания ординат). Тем самым можно свести дело к уже разобранному случаю (проверяться на пересечение будут те же пары отрезков, что и с воображаемой наклонённой прямой).

Время работы.

Если множество S состоит из га отрезков, то время работы алгоритма Any-Segment-Intersect есть O(ralgra). В самом деле, сортировку можно выполнить за такое время (сортировку слиянием или с помощью двоичной кучи), затем мы обрабатываем 2га концов отрезков, тратя на каждый время О (lgra) (таково время любой ис-