Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
7.2. Плоские приложения
351
7.2.4. Пересечение полуплоскостей
Построение общей области N полуплоскостей эквивалентно поиску области решений множества из N линейных неравенств (ограничений) типа
atx-\- bty 4- с i ^ 0, i=l, 2, N. (7.2)
Любое решение (7.2) обычно называется допустимым решением, а все их множество называется допустимой областью. Иллюстрация данной задачи приведена на рис. 7.17.
ограничения \ \
Рис. 7.17. Допустимая область множества линейных ограничений.
Существует простой квадратичный алгоритм для построения пересечения N полуплоскостей. Предположим, что уже известно пересечение первых i полуплоскостей. Это некая выпуклая многоугольная область, ограниченная не более чем i сторонами, хотя и необязательно конечная. Пересечение этой области с очередной полуплоскостью есть не что иное, как ее разрезание прямой линией и сохранение правого или левого куска. Это можно проделать очевидным способом за время 0(i). Суммарная работа потребует 0(N2) времени, однако преимущество данного алгоритма в том, что он открытый.
Рассмотрим вопрос о возможном улучшении алгоритма с помощью метода «разделяй и властвуй». Формальная постановка нашей задачи такова:
Задача С.1.3 (ПЕРЕСЕЧЕНИЯ ПОЛУПЛОСКОСТЕЙ). Даны N полуплоскостей Ни Н2, ..., HN. Нужно построить их пересечение: Н{ (] #2 ("] ... f\HN.
352
Гл. 7. Пересечения
Поскольку оператор пересечения ассоциативен, то его компоненты можно произвольно разбить на части:
Член в левых скобках является пересечением N/2 полуплоскостей и, следовательно, выпуклой многоугольной областью с не более чем N/2 сторонами. То же самое относится и к члену в правых скобках. Поскольку пересечение пары выпуклых многоугольных областей, содержащих по k сторон каждая, можно построить за время O(k) по теореме 7.3, то серединную операцию пересечения в формуле (7.3) можно проделать за время O(N). Отсюда следует такой рекурсивный алгоритм:
procedure ПЕРЕСЕЧЕНИЕ ПОЛУПЛОСКОСТЕЙ
Вход: N полуплоскостей, заданных ориентированными прямолинейными отрезками. Выход: Их пересечение, выпуклая многоугольная область.
1. Разбиение заданных полуплоскостей на два подмножества приблизительно равной мощности.
2. Рекурсивное построение пересечения полуплоскостей для каждой из этих подзадач.
3. Слияние решений этих подзадач путем пересечения двух результирующих выпуклых многоугольных областей.
Если обозначить через T(N) время, используемое этим алгоритмом для построения пересечения полуплоскостей, получаем
Теорема -АЛО. Пересечение N полуплоскостей можно построить за оптимальное время 6(NlogN).
Доказательство. Верхняя оценка следует из уравнения (7.4). Для доказательства нижней оценки покажем, что
СОРТИРОВКА ос„ ПЕРЕСЕЧЕНИЕ ПОЛУПЛОСКОСТЕЙ.
Пусть заданы N действительных чисел х\, xn, и пусть Я,— полуплоскость, содержащая начало координаты и определяемая касательной к параболе у = х2 в точке с координатами (xt, х2.), т. е. прямой у—2х1х — х\ (рис. 7.18). Пересечением таких полуплоскостей является выпуклая многоугольная область, последовательные ребра которой упорядочены по углу наклона. Если построить указанную область, то можно будет считывать заданные {xi) в отсортированном порядке. Теорема доказана.
(Я, П • • • П Ня 12) П (Hn,2+1 П ¦ ¦ • Л Нк).
(7.3)
Т (N) = 2Т (N12) + 0(N) = 0(N log N). Подведем итог:
(7.4)
7.2. Плоские приложения
Общий результат теоремы 7.10 имеет важное приложение-Следствие 7.3. Общую область N выпуклых k-угольников можно построить за время 0(Nk log Л').
Доказательство. Можно прямым методом получить оценку по времени O(NklogNk) путем построения пересечения Nk левых полуплоскостей, ограничивающих исходные многоугольники. Для сокращения этой оценки будем обрабатывать заданные многоугольники как N элементов, а не как набор из Nk ребер. Обозначим через T(N,k) время, необходимое для решения поставленной задачи. Пересечением N/2 штук ^-угольников является выпуклый многоугольник с не более чем Nk/2 сторонами. Пересечение двух таких многоугольников можно построить за время ckN, где с — константа. Поэтому рекурсивно подразби-вая поставленную задачу, получаем, как и в случае задачи ПЕРЕСЕЧЕНИЕ ПОЛУПЛОСКОСТЕЙ:
T(N, k) = 2Т (N12, k) + рис ?л8 Пример того, как СОР-
-f ckN = О (Nk log N), ТИРОВКУ можно преобразовать
в ПЕРЕСЕЧЕНИЕ ПОЛУПЛО-
что и требовалось доказать. СКОСТЕИ.
7.2.5. Линейное программирование с двумя переменными
Постановка задачи (7.2) о пересечении N полуплоскостей (обманчиво) напоминает стандартную постановку задачи линейного программирования [Gass (1969)] для двух переменных. В действительности же последняя задача формулируется так:
Задача С.1.4 (ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ С ДВУМЯ ПЕРЕМЕННЫМИ). Нужно минимизировать функцию ах 4- by, при условии что
atX + btf+Ct^O, i=l,...,N. (7.5)
По-прежнему допустимой областью задачи линейного программирования является множество точек (х, у), удовлетворяющих ограничениям (7.5), которые определяют, очевидно,
354