пользованной нами операции с красно-чёрным деревом). Заметим, что для одной пары отрезков выяснение того, пересекаются они или нет, выполняется за время 0(1).

Упражнения.

35.2-1

Показать, что га отрезков могут иметь 0(га2) точек пересечения. 35.2-2

Даны два непересекающихся отрезка а и Ь, сравнимых относительно х. Используя векторное произведение, определить за время 0(1), выполнено ли соотношение а >х Ь.

35.2-3

Профессор предлагает изменить программу Any-Segment-Intersect так: найдя пересекающиеся отрезки, алгоритм не кончает работу, а продолжает выполнять цикл for. Получившийся алгоритм профессор называет Print-Intersecting-Segments и утверждает, что такой алгоритм напечатает все пересечения отрезков множества в порядке возрастания их абсцисс. Покажите, что профессор дважды неправ: во-первых, алгоритм может напечатать не все отрезки; во-вторых, первая напечатанная им точка может не быть самой левой точкой пересечения.

35.2-4

Постройте алгоритм, который за время О(гаlgra) определяет, имеет ли данная замкнутая га-звенная ломаная самопересечения. 35.2-5

Известно, что два несамопересекающиеся ломаные имеют в сумме га вершин. Постройте алгоритм, который за время О (га lgra) определяет, пересекаются ли они друг с другом.

35.2-6

Даны га кругов, заданных своими центрами и радиусами. Как определить за время О (га lgra), есть ли среди них два пересекающихся (то есть имеющих общую точку)?

35.2-7

Для набора из га отрезков имеется к точек пересечения. За время 0((га + к) lg га) найти все точки пересечения. 35.2-8

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

35.3. Построение выпуклой оболочки

Выпуклой оболочкой (convex hull) конечного множества точек Q называется наименьший выпуклый многоугольник, содержащий

35.6 Выпуклая оболочка CH(Q) множества Q (серый многоугольник)

все точки из Q (некоторые из точек могут быть внутри многоугольника, некоторые - на его сторонах, а некоторые будут его вершинами). Выпуклую оболочку множества Q мы будем обозначать CH(Q). Наглядно можно представлять себе дело так: в точках Q вбиты гвозди, на которые натянута резинка, охватывающая их все - эта резинка и будет выпуклой оболочкой множества гвоздей (рис. 35.6)

В данном разделе мы рассмотрим два алгоритма отыскания выпуклой оболочки множества из га точек; результатом их работы будет список вершин выпуклой оболочки (в порядке обхода против часовой стрелки). Первый из алгоритмов (просмотр Грэхема) требует времени О (га lgra). Второй (проход Джарвиса) выполняется за время О (га/г), где h - число вершин выпуклой оболочки. Как подсказывает рис. 35.6, каждая вершина многоугольника CH(Q) является одной из точек множества Q. Таким образом, для отыскания CH(Q) алгоритм должен решить, какие вершины из Q оставить, а какие - отбросить.

Оба рассматриваемых нами алгоритма (просмотром Грэхема и проход Джарвиса) используют метод «вращающегося луча» (rotational sweep): выбирается полярная системы координат, и точки обрабатываются в порядке возрастания полярных углов (как во вращающемся радаре). Но существуют и другие методы поиска выпуклой оболочки за время О (га lgra); вот некоторые возможности.

Метод добавления точек (incremental method) рассматривает точки слева направо, располагая из в последовательность (pi,р2,Рп) в порядке возрастания абсцисс. На г-ом шаге строится выпуклая оболочка СН (р\, р2,..., pi) первых г точек (к уже известной оболочке первых г - 1 точек добавляется точка рЛ. Эту идею можно превратить в алгоритм, находящий выпуклую оболочку за время О (га lgra) (упр. 35.3-6).

Метод разделяй и властвуй (divide-and-conquer method) за время О (га) делит множество из га точек вертикальной прямой на два примерно равных подмножества, затем рекурсивно ищет выпуклую оболочку каждого из них, а затем объединяет две эти оболочки за время О (га).

Метод стрижки и поиска (prune-and-search method) напоминает алгоритм поиска медианы в упорядоченном множестве за линейное время (раздел 10.3). Он находит «верхнюю цепочку» выпуклой оболочки, повторно отбрасывая некоторую фиксированную долю вершин, пока не останутся только вершины из верхней цепочки. Аналогичным образом ищется нижняя цепочка. Асимптотически

35.7

Работа процедуры textscGraham-Scan для множества Q (рис. 35.6). Для каждого из шагов текущее содержимое стека S показано серым.

(a)Точки (pi,p2, Рт) отсортированы по полярному углу относительно ро! в стеке - первые три точки (po,pi,p2).

(b)- (к) Стек S после очередной итерации цикла for ( строки 7 -10 ). Пунктирными линиями показаны повороты, которые не являются левыми; в этом случае вершина угла поворота удаляется из стека. Например, на этапе (h) из стека сначала удаляется точка ps (правый поворот pipgpg), а затем точка р? (правый поворот РбР7Рэ)-

(1) Результат работы алгоритма - выпуклая оболочка - совпадает с приведённой на рис. 35.6.

этот метод - самый быстрый из известных: если выпуклая оболочка содержит h вершин, то требуется время O(nlgh).

Вычисление выпуклой оболочки важно не только само по себе, но и как промежуточный этап для многих задач вычислительной геометрии. Рассмотрим, например, двумерную задачу о наиболее удалённых точках (farthest-pair problem): дано множество из га точек на плоскости; нужно выбрать пару максимально удалённых друг от друга точек. Можно доказать, что эти точки будут вершинами выпуклой оболочки (упр. 35.3-3); для выпуклого га-угольника можно найти две наиболее удалённые вершины за время О (га) (идея: зажимаем его между двумя параллельными прямыми и вращаем). Тем самым можно найти две наиболее удалённые (из га) точек за время О (га lgra).

Просмотр Грэхема

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

Исходными данными для Graham-Scan является множество Q из (не менее чем трёх) точекг. Процедура используем функцию Top (S), которая возвращает точку, находящуюся в вершине стека S (не меняя содержимого стека), а также функцию Next-To-Top (S), которая возвращает следующий за вершиной элемент стека, также не меняя содержимого. Мы докажем, что по окончании работы в стеке (от дна к вершине) идут как раз вершины CH(Q) (в порядке обхода против часовой стрелки).