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

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

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 134 135 136 137 138 139 < 140 > 141 142 143 144 145 146 .. 180 >> Следующая


Следующим вопросом является вычисление экстремума унимодальной функции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, заставляет полагать, что, прежде чем констатировать факт разрыва между оценками, который мы не можем заполнить, стоило бы попытаться поискать какой-нибудь другой метод решения.
Предыдущая << 1 .. 134 135 136 137 138 139 < 140 > 141 142 143 144 145 146 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed