Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
6.5. Замечания и комментарии
321
сторон многоугольника Р. Это приводит к расширению понятия диаграммы Вороного на некоторое множество отрезков (являющихся сторонами простого многоугольника).
Более сильное обобщение диаграммы Вороного, о котором уже упоминалось в разд. 6.3, заключается в расширении этого понятия на конечное множество точек и открытых отрезков, расположенных произвольным образом. В этом случае ребра диаграммы Вороного являются не только отрезками прямой, но и дугами параболы, так как они отделяют области близости пар объектов следующих типов: (точка, точка), (линия, линия), (точка, линия). Пары последнего типа и порождают дуги парабол. Первые алгоритмы решения этой задачи, близкие к оптимальным, были предложены Драйсдейлом и Ли [Drysdale (1979); Lee (1978); Lee, Drysdale (1981)] (последний из этих алгоритмов имеет сложность 0(N\og2N) для смешанного множества из N объектов). Позднее Киркпатрик [Kirkpatrick (1979)] нашел оптимальное решение задачи со сложностью О (A7 log N). Киркпатрик первым решил важную задачу объединения (слияния) за линейное время диаграмм Вороного двух множеств точек, не разделенных прямой. Затем он использовал этот прием и алгоритм с линейной сложностью для получения минимального остовного дерева планарного графа (см. разд. 6.1) для решения задачи в общей постановке. Заметим, что этот метод неявно решает задачу о срединных осях.
Применение диаграммы Вороного дает изящный метод получения довольно эффективного решения задачи кругового регионального поиска. Задача заключается в следующем: на плоскости заданы множество S, содержащее N точек, и окружность С с центром в точке q (запрос); требуется перечислить точки множества S, попавшие внутрь С. Как обычно для задач регионального поиска, цель заключается в достижении оценки 0(f{N)-\-k), где k — размер множества точек, соответствующих запросу. Если эта цель достижима, то алгоритм характеризуется парой (M(N),f(N)}, где M(N) — требуемый объем памяти. В главе 2 мы уже указывали на неадекватность подходов на основе регионального поиска к данной задаче. Исходную идею использовать диаграммы Вороного следует отнести на счет Бентли и Маурера [Bentley, Maurer (1979)]. Они предложили строить семейство диаграмм Вороного {Vor2;(S): i = 0, 1, ... ¦ Llog2 Л/ J} с последующим просмотром этой совокупности в порядке i = 0, 1, 2.....При просмотре диаграммы определяется область в Vor2((S), содержащая центр окружности q, и проверяется соответствующий список соседей. Просмотр оканчивается, как только обнаруживается, что текущий проверяемый список содержит точку, расстояние до которой от q больше г. Непосредственный анализ показывает, что этот алгоритм
11 Зак. 1075
Гл. 6. Близость: варианты и обобщения
характеризуется парой (N3, logAMog logiV). Недавно эта идея была несколько улучшена [Chazelle, Cole, Preparata, Yap (1986)]. Применение общего подхода «фильтрующего поиска», обсуждавшегося в разд. 2.4, позволило получить алгоритм, характеризуемый парой (N(logjV-loglogAf)2, log Л'').
В разд. 6.1 отмечалось, что минимальное остовное дерево (МОД) множества 5 из N точек на плоскости является подграфом триангуляции Делоне (ТД). Имеются другие интересные геометрические структуры, аналогичным образом связанные с ТД и нашедшие приложения в распознавании образов и кластерном анализе. Это — граф Габриэля и граф относительного соседства. Граф Габриэля (ГТ) множества S определяется следующим образом [Gabriel, Sokal (1969)]: пусть круг (р,-, р/) — круг с диаметром р,р;-; точки р, и р/ множества 5 соединяются ребром в ГГ лишь в случае, когда круг (pi, ру) не содержит внутри точек множества S. Эффективный алгоритм построения ГГ за время O(NlogN) основан на удалении из ТД всех ребер, не пересекающих двойственных им ребер диаграммы Вороного [Matula, Sokal (1980)]. Граф относительного соседства (ГОС) определяется так [Toussaint (1980b)]: точки р< и р, множества S соединяются ребром тогда и только тогда, когда
dist(pj, p/)<ftrnin/(dist(pi, рк), dist(py, рк)).
Это определение означает, что граф содержит ребро (р;, pj) лишь в том случае, когда пересечение двух кругов радиусом длина (piPj) с центрами в точках р,- и р/ не содержит внутри других точек множества 5. Построение ГОС значительно более сложная задача, чем построение ГГ. Суповит [Supowit (1983)] разработал алгоритм со сложностью 0(N\ogN). Между четырьмя упомянутыми графами имеется интересная взаимосвязь: MOD s ГОС cffs TD. (6.7)
В случае плоскости построение этих графов понято довольно хорошо, но для пространств более высокой размерности известно очень мало. В частности, одна из известных открытых задач заключается в разработке и анализе худшего случая алгоритма построения МОД в пространствах размерности три и выше.
Наконец, упомянем класс задач о декомпозиции объектов, заключающихся в разбиении заданного геометрического объекта на совокупность более простых «примитивных» геометрических объектов. Часто такими примитивными объектами являются выпуклые многоугольники, звездные многоугольники и т. д.
