Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Среди таких задач большой интерес представляет задача разбиения внутренности простого многоугольника на треуголь-
6.6. Упражнения
323
ники, т. е. триангуляция простого многоугольника. Очевидно, что для решения этой задачи можно применить общий метод триангуляции с ограничениями, обсуждавшийся в разд. 6.2. Следуя таким путем, мы получим алгоритм, имеющий сложность 0(N\ogN), где N—число вершин многоугольника. Однако, как уже упоминалось ранее, нижняя оценка для задачи триангуляции с ограничениями не применима в данном случае. На протяжении почти десятилетия вопрос о том, можно ли, используя свойство простоты многоугольника, получить алгоритм триангуляции многоугольника, имеющий временную сложность o(N\ogN), оставался без ответа, пока Тарьян и ван Вик [Tarjan, van Wyk (1987)] не разработали алгоритм решения этой задачи, имеющий временную сложность О (N log log N). Однако их результат не исчерпывает вопроса, делая еще более привлекательной цель, заключающуюся в разработке алгоритма с временной сложностью O(N).
По существу, имеются два типа задач, связанных с декомпозицией: задачи разбиения объекта на непересекающиеся части и задачи покрытия, когда получающиеся части могут перекрываться. Иногда в целях декомпозиции объекта на минимальное число частей допускается введение дополнительных вершин, называемых точками Штейнера. Подробное обсуждение задач минимальной декомпозиции содержится в недавнем обзоре Кейла и Сака [Keil, Sack (1985)].
6.6. Упражнения
1. Детально разработать алгоритм построения минимального остовного дерева множества S из N точек на плоскости, использовав для этого пирамиду содержащую ребра триангуляции Делоне множества S. Ребро, извлекаемое из пирамиды, отклоняется или принимается в зависимости от того, образует оно цикл вместе с ребрами, принятыми ранее, или нет. Показать, что время работы этого алгоритма равно Q(N \og N).
2. Привести контрпример к утверждению, согласно которому триангуляция Делоне является минимально взвешенной триангуляцией.
3. Привести контрпример к утверждению, согласно которому жадная триангуляция является минимально взвешенной триангуляцией.
4. Ли. Показать, что в минимальном евклидовом паросочетании (задача Б. 10) отрезки, определяемые парами точек паросочетания, не пересекаются.
5. Зайдель. Пусть S = {х....., %}cR, Показать, что за линейное
время можно построить множество S' — {рь pN) с: R2 вместе с триангуляцией множества 5', где x(pi) = xi, 1 ^ i ^ N.
6. Диаграмма ?-го ближайшего соседа множества S из N точек представляет разбиение плоскости на области (не обязательно внутренне связанные) такие, что каждая область /?, представляет множество точек плоскости, для которых заданная точка р,- е S является k-м соседом (т. е. для любой точки q е Rj длина отрезка qp-, является k-it элементом в упорядоченной в порядке возрастания последовательности длин отрезков qpt, i= 1, N).
324
Гл. 6. Близость: варианты и обобщения
Показать связь диаграммы k-ro ближайшего соседа с диаграммами Vor^-^S) и Vor.(S), k > 1.
7. Показать, что в случае Li-метрики диаграмма Вороного дальней точки множества 5 из Л' точек на плоскости (N > 4) состоит не более чем из четырех областей.
8. Рассмотреть преобразование инверсии на плоскости, отображающее точку v в v' = v(I/|v|2).
(a) Получить уравнение для образа прямой, определяемой уравнением ax-\-by + c = Q (образом прямой является окружность, проходящая через начало координат).
(b) Доказать, что если окружность С содержит внутри начало координат, то внутренность окружности С отображается на внешность ее образа при преобразовании инверсии.
9. Доказать лемму 6.4.
10. На плоскости задано множество S из N точек. Пусть / — прямая, перпендикулярная отрезку plPi, /?,-, р, = 5, и делящая его пополам. Предположим, что / содержит последовательность vb v2, ¦ ¦ ¦, vs вершин диаграмм Вороного, которые перечислены в порядке следования от одного конца прямой к другому. (Каждая вершина и,- является центром окружности, описанной вокруг трех точек множества S.) Покажите, что если луч, заканчивающийся в вершине vu является ребром диаграммы Vorh(S), то луч, заканчивающийся в вершине vs, является ребром диаграммы VorN-h(S).
11. Доказать лемму 6.5.
12. Зайдель. Пусть S = {(хи yt): 1 s? i < #}с: R2 —множество из N точек на плоскости. Обозначим через S1 множество, получающееся в результате проецирования вдоль г-оси множества S на параболоид вращения z = = х* + гД т. е. S1 = {(х{, у{, х\ + yf)- 1 < / < Л'} с R3. Рассмотрим выпуклую оболочку Р множества 5'.
(a) Показать по возможности наиболее прямым способом, что ортогональная проекция на плоскость (х, у) граней оболочки Р, находящихся в «нижней» части Я, совпадает с триангуляцией Делоне множества S.
(b) Обобщить этот результат на случай пространств более высокой размерности.
13. Зайдель. Рассмотрим следующее обобщение диаграмм Вороного (известное под названиями: комплексы ячеек Дирихле, диаграмма Пауэра или диаграмма Лагерра). Пусть 5 — множество из N точек в Е2. С каждой точкой peS связано действительное число гр. Для каждой точки р е 5 опре-
