Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Задача типа С.З (ПОПАРНЫЕ ПЕРЕСЕЧЕНИЯ). Даны N геометрических объектов. Надо определить все их попарные пересечения.
7.1. Примеры из приложений
331
Разумеется, мы будем искать такой алгоритм, при котором не надо сравнивать каждый элемент со всеми остальными. Решение задачи этого типа, которое будет дано в разд. 7.2.3, имеет много практических и теоретических приложений (см. также гл. 8).
7.1.4. Линейное программирование и общее пересечение полупространств
Линейное программирование можно отнести к четвертому типу задачи пересечения. Областью допустимых решений задачи линейного программирования является пересечение полупространств, определенных множеством ее ограничений. Целевая функция достигает максимума в одной из вершин выпуклого полиэдра, способ описания которого отличается от того, что рассматривался в гл. 3. Здесь у нас нет множества точек, среди которых следует найти вершины оболочки, вместо этого имеется набор полуплоскостей, ограничивающих эту оболочку, а нам нужно найти вершины. Очевидно, что после построения общей области для данных N объектов мы сможем получить решение задачи линейного программирования. Однако нам нужно найти лишь ту вершину, на которой целевая функция экстремальна (максимальна или минимальна) и нет оснований полагать, что даже для случая малой размерности необходимо построение всей полиэдральной области.
Одномерная задача линейного программирования тривиальна. Ее можно сформулировать следующим образом:
a*-j-&-»max при atx 4- bt ^ 0, i=\,...,N. (7.1)
Допустимая область тут пуста, является отрезком, или лучом, поскольку возможно такое пересечение лучей, которое продолжается в —со или -f-oo.
Пусть L — самая левая из точек положительно ориентированных лучей, а У? —самая правая из точек отрицательных лучей. Если L > R, то допустимая область пуста. Если L ^ R, то ею является отрезок [L, R]. Очевидно, что L и R можно вычислить за линейное время, поэтому оценка по времени для одномерной задачи линейного программирования пропорциональна O(N). При большем числе измерений задачу линейного программирования можно решить путем построения общей области (пересечения) полупространств. Однако эти две задачи не эквивалентны, как будет показано более точно в разд. 7.2.5.
Теперь обсудим несколько основных алгоритмов, предназначенных для решения вышеописанных задач. Большинство этих алгоритмов создано для задач типа ПОСТРОЕНИЕ ПЕРЕСЕЧЕНИЯ (задачи типа С.1), и тем не менее всюду, где это
332
Гл. 7. Пересечения
уместно, будет проводиться сопоставление с соответствующими задачами типа «проверки». Мы начнем с плоских приложений, а затем перейдем к пространственным примерам. Нужно ли повторять, что уровень знаний в этой области при росте числа измерений отражает картину, знакомую сегодня во всей вычислительной геометрии.
7.2. Плоские приложения
7.2.1. Пересечение выпуклых многоугольников
В данном разделе под «многоугольником» будем понимать его границу и внутренность; цикл из ребер многоугольника будет явно называться его границей. Сформулируем задачу:
Задача С.1.1 (ПОСТРОЕНИЕ ПЕРЕСЕЧЕНИЯ ВЫПУКЛЫХ МНОГОУГОЛЬНИКОВ). Даны два выпуклых многоугольника: Р с L вершинами и Q с М вершинами. Надо построить их пересечение.
Без потери общности положим, что L ^ М.
Теорема 7.2. Пересечением выпуклых L-угольника и М-уголь-ника является выпуклый многоугольник, имеющий не более L -\- М вершин.
Доказательство. Пересечение Р и Q образовано пересечением L -\- М внутренних полуплоскостей, определяемых реб-
рами этих двух многоугольников. Что и требовалось доказать.
Граница Pf\Q состоит из чередующихся цепей вершин этих двух многоугольников, разделенных точками пересечения их границ (рис. 7.4).
Очевидный метод формирования пересечения состоит в обходе границы Р ребро за ребром, в
и безыскусно определяются все точки пересечения с границей Q _(не более двух на каждое ребро) и попутно ведется список то-"чек пересечения и вершин. Это потребует затраты времени O(LM), поскольку будет проверено пересечение каждого ребра Р с каждым ребром Q. Естественно для сокращения вычис-
7.2. Плоские приложения 333
лительной работы попытаться использовать факт выпуклости многоугольников.
Один из подходов заключается в разбиении плоскости на области, в каждой из которых пересечение этих двух многоугольников можно вычислить легко. Построение новых геометрических объектов для решения поставленной задачи не редкость в вычислительной геометрии; читатель может вспомнить исключительное значение этого приема во многих методах геометрического поиска, показанных в гл. 2. В данном случае будет адекватным простейшее разбиение плоскости — индуцированное пучком лучей [Shamos, Ноеу (1976)]. Выберем произвольную точку О на плоскости. (Эту точку О можно взять на бесконечности; в действительности исходный метод Шеймоса — Хоуи основан на выборе О в бесконечности на оси у.) Из О проводим лучи через все вершины многоугольников Р и Q. Эти лучи разбивают плоскость на секторы. Мы хотим упорядочить этот набор лучей по углу вокруг точки О. К счастью, это легко сделать. На самом деле, если О лежит внутри многоугольника, скажем, Р, то лучи к вершинам Р, очевидно, упорядочиваются относительно О так же, как и вершины, порядок которых задан. Если же О лежит вне Р, то вершины Р образуют две цепи (обе они заключены между теми двумя вершинами Р, которых касаются опорные прямые из О), а для каждой цепи соответствующие ей лучи из О отсортированы по углу. Поэтому в любом случае эти секторы, определяемые вершинами Р, упорядочиваются по углу за время, линейно зависящее от числа вершин. Если эти две последовательности (одна для Р и одна для Q) известны, то их можно слить за линейное время.
