Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
9. Ли. Показать, что приведенному выше определению триангуляции Делоне соответствует единственная триангуляция (в предположении, что никакие четыре точки этого множества не лежат на одной окружности).
10. На плоскости заданы два множества точек А и В. Использовать диаграмму Вороного для вычисления
min min dist (a, b)
за время 0(N\ogN), где N = \A\A-\B\ (используется евклидова метрика).
ГЛАВА
Близость: варианты и обобщения
Основной вывод предыдущей главы, состоит в том, что диаграмма Вороного, с одной стороны, является чрезвычайно универсальным средством для решения ряда фундаментальных задач о близости точек, с другой стороны, она сама представляет необычайно привлекательный математический объект. И именно эти две стороны — инструментальная и эстетическая— явились источником вдохновения для многочисленных исследований в этой области. В этой главе мы продемонстрируем результаты таких исследований. Начнем с обсуждения двух очень важных приложений: с упоминавшейся уже задачи о евклидовом минимальном остовном дереве (и некоторых ее вариантах) и задачи о триангуляции плоскости в общей постановке. Затем будут показаны различные обобщения понятия локуса. Завершается глава анализом класса задач, касающихся покрытий множеств, что позволит оценить возможности различных моделей вычислений.
6.1. Евклидовы минимальные остовные деревья
В предыдущей главе была рассмотрена задача о евклидовом минимальном остовном дереве (ЕМОД, задача Б.5, разд. 5.1) и было показано, что задача СОРТИРОВКА сводима к ней за линейное время. Это дает нижнюю оценку Q(NlogN) для времени построения ЕМОД множества из N точек. В этом разделе будет показано, что эта оценка алгоритмически достижима.
Алгоритм, который будет описан, как и любой известный алгоритм поиска минимального остовного дерева в произвольном графе, основывается на следующей довольно очевидной лемме:
6.1. Евклидовы минимальные остовные деревья
277
Лемма 6.1 [Prim (1957)] Пусть G =(V, Е)— граф со взвешенными ребрами, а {V\, V2} — разбиение множества V. В G имеется минимальное остовное дерево, содержащее кратчайшее из ребер, одна вершина которого принадлежит V\, а другая V2.
В нашем случае множество вершин V — это множество точек S, а длина ребра равна евклидову расстоянию между его конечными точками. На каждом шаге построения ЕМОД алгоритм будет обрабатывать лес, содержащий несколько деревьев (которые впоследствии станут поддеревьями получающегося в результате ЕМОД). Первоначально лес представляет совокупность вершин (т. е. каждая точка представляет отдельное дерево без ребер). Основной шаг алгоритма выполняется следующим образом (здесь d(u,v) обозначает длину отрезка uv):
(1) Выбрать из леса некоторое дерево Т.
(2) Найти ребро (u',v') такое, что d(u', v') = mm{d(и, и): u 6Е Г, о ев S — Т}.
(3) Если Т—-дерево, содержащее v', то объединить Т и Т, соединив их ребром (u',v'). Выполнение алгоритма завершается, когда лес содержит единственное дерево, являющееся ЕМОД исходного множества точек.
Хотя реализация операций (1) и (3) требует большой тщательности, основные трудности рассматриваемого метода связаны с выполнением операции (2).
Действительно, возникает интуитивное опасение, что объем работы, необходимой для ее выполнения, пропорционален 17" IX^-I ). что соответствует перебору всех пар вершин, одна из которых принадлежит Т, а вторая берется из оставшейся части. К счастью, благодаря следующей лемме, здесь нам на помощь приходит диаграмма Вороного.
Лемма 6.2. Пусть S — множество точек на плоскости, а А(р) обозначает множество точек, смежных с peS в триангуляции Делоне множества S. При любом разбиении {Su S2} множества S, если qp — кратчайший отрезок, соединяющий точки из S\ и S2, то q принадлежит А(р).
Доказательство. Пусть на отрезке pq достигается минимальное расстояние между точками S, и 52 и при этом peSi, a q^S2 (рис. 6.1). Утверждается, что q^A(p). Если q^A(p), то перпендикуляр к отрезку pq, делящий его пополам, не содержит отрезка границы V(р)~ многоугольника Вороного точки р (теорема 5.9). Отсюда следует, что V(p) пересекает pq в некоторой точке щ_ расположенной между р и точкой М — серединой отрезка pq. Ребро / диаграммы Вороного, содержащее точку и, перпендикулярно отрезку рр', р' se S и делит его
278
Гл. 6. Близость: варианты и обобщения
пополам. При любом возможном выборе и и / положение точки р' ограничивается внутренностью круга С с центром в точке М и диаметром qp. Возможны два случая: (1) р' <=е Su в этом случае d{q, р') < d(q, р), так как ближе к q находится р', а не р (противоречие); (2) р' е S2, в этом случае d(p, р')< <d(q,p), так как р' ближе к р, чем q (снова противоречие).
Другими словами, согласно этой лемме, необходимо просматривать лишь ребра триангуляции Делоне, т. е. необходимо искать минимальное остовное дерево планарного графа [Shamos (1978)].
Вернемся вновь к реализации основного шага алгоритма построения ЕМОД. Черитон и Тарьян [Cheriton, Tarjan (1976)] предложили в числе других методов следующую простую стратегию. Для выбора дерева Т (которое будет объединено с дру-
