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

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

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


В этой главе триангуляция Делоне была введена как некоторый попутный результат, получаемый при построении диаграммы Вороного. Однако можно определить триангуляцию Делоне как единственную триангуляцию, обладающую тем свойством, что окружность, описанная вокруг любого треугольника, не содержит внутри ни одной другой точки. Исходя из такого определения, можно непосредственно построить триангуляцию Делоне, использовав для этого рекурсивную процедуру, аналогичную приведенной процедуре построения диаграммы Вороного. Как показали Ли и Шехтер [Lee, Schachter, (1980)], время работы такой процедуры соответствует оптимальной оценке. В действительности этот подход был предложен для случая Li-метрики, так как для этой метрики диаграмма Вороного уже не является единственной и вследствие этого нарушается связь между диаграммами Вороного и триангуляцией Делоне.

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

274

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

d(A, B) = minmmd(a, b), где а<=Л, JeS и d — евклидово

расстояние. При таком определении d(A, В) = d(B, А). Другая мера, представляющая интерес и не являющаяся симметричной, это хаусдорфово расстояние [Grunbaum (1967)]. Хаусдорфово расстояние от Л до Б равно maxmin d(a, Ь), а хаусдорфово

расстояние между двумя множествами Л и В равно max{d(A, В), d(B, А)}. В случае конечных множеств А и В задача БЛИЖАЙШАЯ ПАРА МЕЖДУ МНОЖЕСТВАМИ может быть решена с использованием диаграммы Вороного в оптимальное время Q(N \ogN). Можно ожидать, что в случае, когда точки множества являются вершинами выпуклого или простого многоугольника, существует более быстрый алгоритм решения. Аталла [Atallah (1983)] рассматривает хаусдорфово расстояние между двумя выпуклыми многоугольниками и дает алгоритм его вычисления, имеющий сложность O(N). Шварц [Shwartz (1981)] рассмотрел задачу поиска ближайшей пары точек двух выпуклых многоугольников (двух множеств, не являющихся конечными) и предложил алгоритм со сложностью 0(log2iV). Впоследствие этот результат был улучшен до O(logiV) [Edelsbrunner (1982); Chin, Wang (1983)]. Для поиска ближайшей пары вершин двух выпуклых многоугольников необходимо и достаточно времени O(N) [Chin, Wang (1984); Toussaint (1983a)].

5.8. Упражнения

1. Ли. На плоскости заданы два множества А к В, содержащие по N точек каждое. Найти две ближайшие точки, одна из которых принадлежит А, а другая В. Показать, что для этого требуется Q(N\ogN) операций. Что изменится, если множества А и В линейно разделимы?

2. Ли. На плоскости заданы два множества точек А и В, каждое из которых образует «лестницу» (т. е. каждое множество совпадает с множеством своих максимумов в отношении доминирования; см. разд. 4.1.3).

(a) Найти пару точек (puPi), где р,-еЛ и р,^В, ближайшую по /.рметрике.

(b) Можно ли это сделать за линейное время?

3. Обращение диаграммы Вороного. Задана планарная карта валентности 3 с N вершинами (каждая вершина имеет степень 3). Разработать эф-

5.8. Упражнения

275

фективный алгоритм, проверяющий, является ли эта карта диаграммой Вороного некоторого конечного множества точек 5. В случае положительного ответа алгоритм должен в явном виде построить множество S.

4. Диаграмма Вороного на сфере. На трехмерной сфере S3 задано множество S из jV точек. Рассмотреть диаграмму Вороного S3-Vor(S) множества S, построенную на сфере S3 с использованием евклидовой метрики.

(a) Показать, что каждое ребро диаграммы S3-Vor(S) является дугой большой окружности сферы S3.

(b) Предположим, что все точки множества S находятся на полусфере сферы S3 (все точки находятся по одну сторону от некоторой плоскости, проходящей через центр сферы S3).

Показать, как можно использовать алгоритм построения диаграммы Вороного на плоскости (см. разд. 5.5) для построения S3-Vor(S).

5. (а) Охарактеризовать диаграмму Вороного множества из N точек на плоскости в случае использования ?гметрики.

(b) Тот же самый вопрос для /.«.-метрики.

(c) Какова взаимосвязь диаграмм Вороного, построенных для метрик Ьх и /.«.?

6. В случае 12-метрики точки множества S, многоугольники Вороного которых не ограничены, образуют выпуклую оболочку множества S (теорема 5.10). Имеет ли место то же самое для Ii-метрики?

7. Сформулировать и доказать теорему, аналогичную теореме 5.8, для L, -метрики.

8. Ли. Рассмотреть следующее определение триангуляции Делоне множества из N точек, никакие четыре из которых не лежат на одной окружности. Две точки pi и pf определяют ребро триангуляции Делоне тогда и только тогда, когда существует окружность, проходящая через эти две точки и не содержащая внутри никаких других точек множества. Показать, что это определение дает триангуляцию, удовлетворяющую условию: окружность, описанная вокруг любого треугольника, не содержит внутри никаких других точек множества. Следовательно, это то же самое, что и граф двойственный диаграмме Вороного этого множества точек.
Предыдущая << 1 .. 95 96 97 98 99 100 < 101 > 102 103 104 105 106 107 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed