Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Очевидно, что =0(kN). Отсюда следует, что Vorfe+i(5) может быть получена из Vork(S) за время O(kNlogN), а суммарное время построения Vorfe+i(5), начиная с S, равно
к-1
? О (iN log N) = 0 (k2N log N). Следующая теорема подводит итог сказанному:
Теорема 6.10. Диаграмма Вороного порядка k множества из N точек может быть построена за время 0(k2NlogN).
Такой подход можно было бы применить для построения всех диаграмм VorA(S), k=\, N—1, на что потребовалось бы время О (Л/3 log Л/). Однако, используя недавно разработанный подход [Edelsbunner, Seidel (1986)], основанный на теории, в общих чертах представленной в разд. 6.3.1.2, можно построить разбиение пространства, определяемое семейством {п(р): peS} плоскостей, касательных к параболоиду затратив на это время, пропорциональное числу пересечений, образуемых тремя плоскостями, т. е. за 0(N3). Таким образом, имеет место теорема 6.11:
Теорема 6.11. Совокупность всех диаграмм Вороного высших порядков множества из N точек можно построить за время 0(N3).
Этот раздел мы завершаем двумя замечаниями. Первое — задача Б.6 о поиске ^-ближайших соседей сводится к задаче определения положения точки в диаграмме Vork(S). Время решения этой задачи включает время поиска — определение положения в Vor&(S)—и время выдачи ответа. Очевидно, что последнее равно 0(k), в то время как первое пропорционально log Vk, где Vk — число вершин диаграммы Vor*(S). Вспоминая, что Vk = Vl^) + V^)_l и что V^ = 0(kN), получаем, что поиск k ближайших соседей выполняется за время О (log kN-\-k) = = О (log N-\-k). Подводя итог сказанному, получаем следующую теорему (см. в разд. 2.2 соответствующий результат для поиска):
Теорема 6.12. Если на плоскости задана некоторая точка, то k ее блиокайших соседей из числа N точек могут быть найдены за время 0(logN-\-k) с использованием предварительной обработки с временем О (k2N log N).
Второе замечание состоит в том, что понятие обобщенной диаграммы Вороного объединяет задачи о ближайшей и даль-
6.3. Обобщения диаграммы
309
ней точках, так как множество точек, k ближайших соседей которых составляют множество Т, является также множеством точек, для которых N — k наиболее удаленных от них точек составляют множество S — Т. Таким образом, диаграмма ближней точки порядка k в точности совпадает с диаграммой дальней точки порядка (N — k). Давайте рассмотрим одну из них более
Рис. 6.17. Диаграмма Вороного дальней точки.
подробно, а именно диаграмму ближней точки порядка (N — 1) или, что эквивалентно, диаграмму дальней точки порядка 1 (рис. 6.17).
С каждой точкой р, связана выпуклая многоугольная область VN-i(pi) такая, что р,- наиболее удалена от каждой точки в этой области. Эта диаграмма определяется только точками выпуклой оболочки, так что в ней отсутствуют ограниченные области. Конечно, Vorjv_i(S) можно построить, применив непосредственно описанный общий метод. Однако в этом случае время решения задачи составило бы 0(N3) (по теореме 6.12). Необходимо отметить, что существует прямой метод, основанный на подходе «разделяй и властвуй», аналогичный алгоритму построения диаграммы ближней точки, позволяющий получить результат за оптимальное время 0(Л' logN) [jjliarnos Ц978); Lee^ (1980b)J. Если уже найдены диаграммы левой' и правой половин множества, то разделяющая ломаная линия а обладает теми же свойствами, что и в случае диаграммы ближней точки. Однако к этому моменту должны быть удалены все части ребер диаграммы VorN-\(S\), лежащие слева от а, а также части ребер диаграммы Уоглг_, (S2), лежащие справа от а. В следующем разделе у нас еще будет возможность обсудить очень тесную связь, существующую между Von(S) и Vorw_i(S).
Гл. 6. Близость: варианты и обобщения
6.3.2. Диаграммы Вороного ближней и дальней точек в многомерных пространствах
Как мы уже видели ранее, обобщенные диаграммы Вороного (всех порядков) на плоскости имеют топологию пла-нарных графов. Из этого следует, что число вершин, число граней и число ребер диаграммы имеют один и тот же порядок. Это позволяет разрабатывать оптимальные по времени
(а) (Ъ)
Рис. 6.18. Пример множества из N точек в трехмерном пространстве, диаграмма Вороного которого имеет Q(N2) ребер.
алгоритмы построения диаграмм Вороного ближней и дальней точек.
Можно ли получить такой же результат для пространств размерности, большей двух? Все надежды на это тут же рушатся, если учесть, что диаграмма Вороного ближней точки множества из ./V точек в трехмерном пространстве может иметь 0(N2) ребер [Preparata (1977)]. Легко построить пример, обладающий этим свойством (рис. 6.18). Пусть Si — множество из N/2 точек, равномерно расположенных на окружности, лежащей в плоскости (х,у), центр которой находится в начале координат. Кроме того, пусть S2 — множество из N/2 точек, равномерно расположенных на г-оси, по N/4 точек выше и ниже начала координат. Положим S = Si U S2. Утверждается, что любой отрезок, соединяющий некоторую точку множества Si с некоторой точкой множества S2, является ребром графа Делоне, т. е. оно является двойственным некоторому многоугольнику диаграммы Вороного (грани некоторого политопа диаграммы Вороного). Это хорошо видно на сечении диаграммы
