Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
l°Kl(l-a)/v
г(Л0< ? /С(1-а)'-Ч<-^-.
т. е. оно линейно зависит от N, и это оптимально! Сейчас будет показано, что можно получить величину а= 1/4.
Рис. 7.22. Иллюстрация возможных случаев, при которых F^(X)> F+(X).
На начальной стадии пусть /_ и /+ будут множествами индексов, определенных ранее, а |/+| + |/-| = М (т. е. на этой стадии имеется М активных ограничений, разбитых на два множества 5+ и S-). Разобьем каждое из множеств S+ и 5_ на пары ограничений, причем по одному ограничению в каждом множестве может остаться без пары. Допустим i, и об-
ратимся к рис. 7.23. Если 6; = б/, то соответствующие прямые параллельны и одну из них можно сразу удалить (в данном случае ту, у которой больше значение у) (рис. 7.23(a)). В про-
7.2. Плоские приложения
тивном случае, обозначив через Хц абсциссу точки пересечения ограничений, имеем следующие три случая: если Хц <. и\, то удаляем ограничение с большим значением б (рис. 7.23(b)); если > и2, то удаляем ограничение с меньшим значением б (рис. 7.23(c)); если же щ ^ Хц ^ «2, то ничего не удаляем
(с) (d)
Рис. 7.23. Для каждой пары ограничений находим, к какому из этих четырех случаев она относится, после чего одно из ограничений удаляется.
(рис. 7.23(d)). Затем точно так же обрабатывается множество 5_. Для тех пар, ни один из членов которых не был удален, вычисляем абсциссу точки их пересечения.
Итак, если k ограничений были удалены сразу, то получаем множество из ЦМ — k)/2\ абсцисс пересечений, причем тратим на это О(М) времени. Затем применяем к этому множеству абсцисс алгоритм поиска медианы [Blum, Floyd, Pratt, Rivest, Tarjan (1973); Schonhage, Paterson, Pippenger (1976)], обладающий линейной оценкой по времени, и получаем его медиану X. Значение X является абсциссой, для которой проводится очередное «вычисление»; очевидно, что эта операция займет О(М) времени. Если в точке X нет экстремума, то поло-
362
Гл. 7. Пересечения
вина из вычисленных абсцисс {А,-/} лежит в той области, о которой известно, что в ней нет экстремума. Для каждого Хц из этой области можно удалить одно ограничение из пары непосредственно. (Например, если Xi,- находится слева от X, а оптимум— справа, то из пары прямых, пересекающихся в Xi,-, удаляем ту, у которой меньше наклон, и т. д.) Завершаем шаг алгоритма с тем результатом, что удалено не менее k + + Г L Щ — &)/2]/2l;5s L-M/4J ограничений. Это подтверждает получение ранее обещанного значения а =1/4, и мы имеем следующий удивительный результат:
Теорема 7.12. Задачу линейного программирования с двумя переменными и N ограничениями можно решить за оптимальное время Q(N).
Как упоминалось ранее, этот метод можно модифицировать для соответствующей трехмерной задачи, опять получая алгоритм с оптимальной оценкой по времени 0(Л/). Читатель отсылается к ранее цитированным статьям Меджиддо и Дайера для изучения деталей этого замечательного метода.
Замечание 1. Как показал Меджиддо, общий метод, описанный выше, можно применить к немного отличающимся ситуациям. Одним из таких примеров является вычисление наименьшей окружности, охватывающей множество 5 = {pi, р2, ..., Pn}, состоящее из N точек, где р, = (x,-,yi). Как показано в разд. 6.4, определение наименьшей охватывающей S окружности означает вычисление
Если ввести переменную г, то выражение (7.8) можно переформулировать как следующую задачу математического программирования:
( минимизировать z
(Заметим, что значение координаты z в точке решения равно квадрату радиуса этой окружности.) Задача (7.9) не является задачей линейного программирования, поскольку ее ограничения являются квадратичными. Однако исходное ограничение можно переписать в виде
где с. =± х\-\-у\. Отсюда видно, что правая часть (7.10) состоит из линейного выражения —2х,х — 2у,у + с,, зависящего от /, и из квадратичной составляющей {х2-\-у2), не зависящей от j.
(7.8)
при условиях г > (xt — х)2 + (yt — у)2, i = 1, . . ., N.
(7.9)
z > - 2xiX - 2yitj + cL + (x2 + у2),
(7.10)
7.2. Плоские приложения
Множество линейных ограничений z> — 2xtx — 2у,у + a, г = 1, 2.
(7.11)
определяет полиэдр, граница которого задается уравнением z = f(x,у), где /—выпуклая вниз функция. Поскольку (х2 + + у2) — тоже выпуклая вниз функция, то функция <р (*,«/) А f (х> У) + *2 + У2 является суммой двух выпуклых вниз функций. В качестве простого упражнения читатель может проверить сходство поверхности z = <p(x,y) с полиэдральной поверхностью в том смысле, что она имеет вершины, образованные пересечением трех1) дуг парабол (ребер), лежащих в вертикальных плоскостях, и что ее гранями являются участки поверхностей параболоидов. Двумерной иллюстрацией служит рис. 7.24. Простой анализ позволяет убедиться, что описанный выше метод удаления ограничений полностью применим также к данной ситуации. Единственное существенное различие заключается в том, что вершина до, доставляющая минимальное значение z (среди других вершин), может не совпадать с искомым минимумом (хотя в случае линейного программирования эти минимумы всегда совпадают). Поэтому поиск завершается проверкой тех «ребер» функции z = f(x,у), которые инцидентны вершине до, и, если это необходимо, локализацией минимума на одном из этих ребер.
