Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Следующим вопросом является вычисление экстремума унимодальной функции1) (заметим, что выпуклая функция унимодальна). Хорошо известен и прост тот факт, что экстремум унимодальной функции, определенной на N дискретных точках действительной оси, можно определить методом модифицированного двоичного поиска, проведя O(logjV) вычислений функции и O(logiV) сравнений.
Рис. 7.38. Иллюстрация функций d(v) и y(xi). Показано сечение Р и Q плоскостью Х\ = Х\.
Теперь можно сформулировать третий шаг поиска, предположив без потери общности, что L ^ М:
Шаг 3. Отсортировать множество {xi: xi = xi(v), где v — вершина на нижней стороне Р} в порядке возрастания; обозначим через V упорядоченную последовательность. Поскольку у(хх) унимодальна на последовательности V, то надо найти единственный отрезок *"], ограниченный точками из V, который гарантированно содержит минимум у(Х]) при х^.Х\. (Очевидно, что этот поиск прекратится, если будет найдено такое значение хи при котором у(х{) = 0.)
Чтобы проанализировать время работы шага 3, заметим прежде всего, что O(LlogL) времени уйдет на начальную сортировку абсцисс. Затем для заданного х\ вычисление у(х{)
') Функция f(x) называется унимодальной вниз на интервале [лС|,х2], если существует такое х0 е [хи х2], что f(x) не возрастает на [xt,x0] и не убывает на [х0, х2]. Аналогично определяется и унимодальная вверх функция.
Верх [eQ()~\
382
Гл. 7. Пересечения
можно выполнить за время O(N) методом, который был описан ранее. Наконец, благодаря унимодальности у на Хх методом модифицированного двоичного поиска получаем отрезок [х{, х"], вычислив у О (logL) раз. Итак, общее время работы составляет ровно 0(L logL) + 0(N logL) = 0(N logL).
Заметим теперь, что по построению отрезок [хр х"] не содержит внутри себя абсцисс вершин нижней стороны Р. Поэтому полоса x^^Xj^x" не содержит внутри себя ни одной вершины Gp, а, значит, множество <% из ребер GP, пересекающих эту полоосу, можно упорядочить (рис. 7.39). Рассмотрим
Рис. 7.39. Часть проекции нижней стороны Р на плоскость х3 = 0 в пределах полосы [xj, *"]. Внутри этой полосы нет вершин графа GP.
такое ребро е из GQ, которое имеет непустое пересечение с полосой xJ^Xj^x". Функция d{xi,x2) вдоль этого ребра выпукла вниз, а ее минимум совпадает с одной из вершин графа G* (эта вершина является либо одним из концов е, либо точкой пересечения е с одним из ребер &). Поскольку последние ребра упорядочены, то этот минимум можно определить весьма эффективно. Действительно, предположим, что элементы <g организованы в дереве двоичного поиска элементарными операциями которого являются определение точки пересечения v пары ребер и вычисление функции d(v) (эти операции реализуются за время 0(1)). Кроме того, для обработки одного ребра из GQ требуется О (logL) времени, что следует из предшествовавшего обсуждения свойств унимодальных функций. Итак, получен последний шаг процедуры поиска:
Шаг 4. Определить минимум функции d(xux2) на каждом ребре е из Gq, которое пересекает полосу х^^х^х". Наименьший из этих минимумов является глобальным минимумом d на 3). (Вновь заметим, что поиск прекращается, если обнаружено такое ребро, на котором минимум d неположителен.)
Поскольку число ребер, обработанных па шаге 4, не превосходит числа ребер в q (равного 0(М)), а обработка одного ребра требует О (logL) времени, то шаг 4 завершается за время
х,=х,
Множество ? из. pedep Gp
7.3. Трехмерные приложения
383
O(MlogL). Отмечая, что, поскольку и L<N, и M<N, постольку потребуется О (NlogN) времени на обнаружение или такой точки и, для которой d(u)^0, а следовательно, она принадлежит P{]Q, или факта пустоты множества P(]Q. Объединяя этот результат с ранее полученным результатом, который относился к построению PflQ при условии, что одна из его точек известна, получаем следующую теорему:
Теорема 7.15. Пусть даны два выпуклых полиэдра: Pel вершинами и Q с М вершинами; обозначим М = L + М.Для построения их пересечения PflQ нужно затратить О (NlogN) времени.
К сожалению, единственная нижняя оценка, которую мы можем предложить для этой задачи, тривиальна —Q (Л/). Поэтому неизвестно, является ли результат теоремы 7.15 оптимальным. На сегодняшний день небезосновательно предположение, что может существовать метод решения этой задачи, обладающий линейной оценкой по времени.
7.3.2. Пересечение полупространств
Самым естественным подходом к решению любой трехмерной задачи является попытка обобщения наиболее известного метода решения соответствующей двумерной задачи. В нашем случае двумерным аналогом является задача о пересечении полуплоскостей, решенная в разд. 7.2.4 методом «разделяй и властвуй», на шаге «слияние» которой решалась задача о пересечении двух выпуклых многоугольников. Соответственно в случае трех измерений шагом слияния становится пересечение двух выпуклых полиэдров, которое изучалось в предыдущем разделе. Однако если пересечение двух выпуклых многоугольников с L и М вершинами (где L + MA,N) можно построить за время Q(N), то пересечение двух выпуклых полиэдров с аналогичными параметрами строится уже за время О (NlogN). Поэтому обобщение двумерного алгоритма дало бы оценку О (N log2 N). Противопоставление этого результата нижней оценке Q (NlogN), полученной в разд. 7.2.4, заставляет полагать, что, прежде чем констатировать факт разрыва между оценками, который мы не можем заполнить, стоило бы попытаться поискать какой-нибудь другой метод решения.