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

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

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 94 95 96 97 98 99 < 100 > 101 102 103 104 105 106 .. 180 >> Следующая


Теорема 5.18. Триангуляция, в которой окружность, описанная вокруг любого треугольника, не содержит других точек, может быть найдена за время 0 (JV log Л/), что является оптимальным для любой триангуляции.

Хотя диаграмма Вороного может быть использована для получения в оптимальное время триангуляции множества точек и, следовательно, для решения задачи Б.4, задача о пла-нарной триангуляции в своей общей формулировке является

5.6. Решение задач о близости с помощью диаграммы Вороного 271

значительно более широкой, и мы еще вернемся к ней в разд. 6.2. Кроме того, в одном из следующих разделов будет рассмотрена интересная взаимосвязь задач ЕВКЛИДОВО МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО и ДИАГРАММА ВОРОНОГО.

Здесь уместно вновь вернуться к диаграмме, представленной на рис. 5.6 и отражающей взаимосвязи между задачами о близости точек. На рис. 5.30 эта диаграмма показана с учетом результатов, приведенных в данном разделе. На этой диаграмме также отражен известный факт о том, что задача СОРТИРОВКА сводима за линейное время к задаче ДИАГРАММА

Рис. 5.31. Построение выпуклой оболочки по диаграмме Вороного.

ВОРОНОГО (теорема 5.12), и показано новое сведение задачи ВЫПУКЛАЯ ОБОЛОЧКА к задаче ДИАГРАММА ВОРОНОГО, устанавливаемое следующей теоремой:

Теорема 5.19. Если имеется диаграмма Вороного множества из N точек на плоскости, то выпуклая оболочка этого множества может быть найдена за линейное время.

Доказательство. Пусть диаграмма Вороного представлена РСДС с ориентацией обхода циклов, составляющих грани, например, против часовой стрелки. Будем перебирать ребра диаграммы до тех пор, пока не найдется луч (рис. 5.31). Если считать г ориентированным в направлении от бесконечности к его началу и при этом многоугольник V(i) расположен справа от луча г, то точка р, является вершиной выпуклой оболочки (теорема 5.10). Будем просматривать ребра многоугольника V(i) до тех пор, пока не встретится другой луч г'. Изменив на обратную ориентацию луча г, определим следующую вершину выпуклой оболочки pi и теперь будем просматривать ребра

272

Гл. 5. Близость: основные алгоритмы

многоугольника V(j) и т. д., пока вновь не вернемся к многоугольнику V(i). Ребро диаграммы просматривается лишь в том случае, если выполняется обход ребер одного из многоугольников, содержащих это ребро. Так как каждое ребро принадлежит в точности двум многоугольникам, то ни одно ребро не будет просмотрено более двух раз и время обработки является линейным.

Действительно, замечательно, что такая разнородная совокупность задач может быть решена с использованием единственной структуры. Однако возможности применения диаграммы Вороного не ограничиваются рассмотренными. При обсуждении в последующих разделах других приложений мы не перестанем удивляться многообразию использования диаграммы Вороного.

5.7. Замечания и комментарии

Результаты, обсуждавшиеся в предыдущих разделах этой главы, относились к задачам о близости точек в пространствах с евклидовой метрикой. Евклидова метрика может быть легко обобщена до понятия Lp-метрики (метрики Минковского), определяемой следующим образом:

Определение 5.3. Lp-расстояние между двумя точками q\ и q2 в евклидовом пространстве Ed с координатами х\, х2, ха для произвольного действительного числа 1 ^ р ^ оо определяется следующей формулой:

dP (?i, <?2) = ( Z I х, (<?,) - х, М {"J". (5.4)

Таким образом, традиционная евклидова метрика совпадает с /,2-метрикой. Все задачи, обсуждавшиеся ранее, можно рассматривать и в случае Lp-метрики для произвольного р, и такое исследование было проведено в числе прочих Ли и Вонгом [Lee, Wong (1980)] и Хвангом [Hwang (1979)]. Помимо Z-2-расстояния особый интерес представляют Li-расстояние (известное также под названием манхвттенское расстояние) — длина кратчайшего пути, каждый участок которого является отрезком, параллельным одной из осей координат, и Loo-расстояние, определяемое максимальной разностью координат. Эти метрики являются естественными для целого ряда приложений, таких как моделирование движений руки и проектирование топологии интегральных схем.

Естественно ожидать, что сужение некоторой задачи на ограниченный класс данных позволит получить более эффек-

5.7. Замечания и комментарии

273

тивный алгоритм ее решения. Примером такого ограничения служит ситуация, когда все N точек множества S являются вершинами выпуклой оболочки. В этом случае использование свойства выпуклости позволяет решить задачу ВСЕ БЛИЖАЙШИЕ СОСЕДИ в оптимальное время Q(N) [Lee, Preparata (1978)]. Около десяти лет вопрос о существовании алгоритма построения диаграммы Вороного выпуклого многоугольника с временем обработки 6(N) оставался одним из животрепещущих вопросов вычислительной геометрии. Лишь недавно был получен положительный ответ на этот вопрос [Aggarwal, Guibas, Saxe, Shor (1987)]. Предложенный ими метод основывается на рассмотренном в разд. 6.3.1.2 соответствии между диаграммами Вороного множества S из N точек, лежащих в плоскости 2=1, и разбиением пространства, определяемого плоскостями, касательными к параболоиду г — х2 + у2 -f- 1 в точках {(хр г/., х\ + у] + 1): (х., г/.) eS}. В частности, проекция на плоскость z = 1 пересечения соответствующих полупространств, определяемых этими плоскостями, дает диаграмму Вороного ближней точки множества S. Если 5 — это множество вершин выпуклого многоугольника Р, лежащего в плоскости 2=1, то этот метод дает диаграмму Вороного многоугольника Р. Ключевым моментом является тот факт, что знание порядка следования вершин при обходе границы многоугольника Р позволяет разработать хитроумный алгоритм вычисления требуемого пересечения полупространств за линейное время.
Предыдущая << 1 .. 94 95 96 97 98 99 < 100 > 101 102 103 104 105 106 .. 180 >> Следующая

Реклама

Аренда мини экскаватора

Аренда мини экскаватора, мини погрузчика, вся техника оснащ. гидромолотом

arenda-mini-ekskavatora.ru

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed