Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 130

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 124 125 126 127 128 129 < 130 > 131 132 133 134 135 136 .. 180 >> Следующая


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
Предыдущая << 1 .. 124 125 126 127 128 129 < 130 > 131 132 133 134 135 136 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed