Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
ченный результат. И, как обычно, для ответа на этот вопрос обратимся к одномерному случаю. В этом случае задача сводится к поиску на прямой пары последовательных точек, максимально удаленных друг от друга (МАКСИМАЛЬНЫЙ ПРОМЕЖУТОК), так как в одномерном случае окружность вырождается в отрезок. Нижняя оценка Q(N\ogN) времени решения этой задачи, полученная Мэнбером и Томпа [Manber, Тотра (1982)] для модели линейных деревьев решений, недавно была расширена Ли и By [Lee, Wu (1986)] на более общую математическую модель вычислений. (Их результат основывается на сведении задачи МАКСИМАЛЬНЫЙ ПРОМЕЖУТОК к задаче ОДНОРОДНЫЙ ПРОМЕЖУТОК, рассматриваемой как задача-прототип.) Это контрастирует со следующим самым неожиданным результатом, полученным Гонза-лесом [Gonzales (1975)]: если изменить модель вычислений,
ствуя таким образом, можно найти все точки пересечения Vor(S) с CH(S).
Рис. 6.21. Пример обхода диаграммы Vor(S) при определении пересечений Vor(S) с conv(S).
При таком обходе каждый посещаемый отрезок диаграммы Vor(S) проходится не более двух раз. Так как, согласно свойству 2, каждое ребро имеет не более двух таких отрезков, то каждое ребро проверяется самое большее четыре раза, и, следовательно, пересечение диаграммы Vor(S) с оболочкой CH(S) вычисляется за время О (Л/)1).
Здесь может появиться желание узнать, насколько оптимален полу-
') Описанный подход связан с аналогичным результатом, полученным Туссэном [Toussaint (1983b)].
6.4. Промежутки и покрытия
319
то задачу можно решить даже за линейное время. Изменение заключается в добавлении к стандартному набору функций функции вычисления целой части « [ J» (которая не является аналитической). Здесь мы приводим этот выдающийся алгоритм Гонзалеса:
ргосеаигеМАКСИМАЛЬНЫЙ-ПРОМЕЖУТОК
Входные данные: N действительных чисел : /V] (числа не упорядочены)
Выходные данные: MAXGAP — длина наибольшего
промежутка между последовательной парой чисел упорядоченного множества
begin MIN :=minX[t];
МАХ:=тах*И; ')
(* разбить интервал между точками MIN и МАХ на N—1 равных отрезков. Массивы HIGH и LOW используются для хранения соответственно наибольшего и наименьшего значений на отрезках *) for i := 1 until N — 1 do begin COUNT[i]:=0;
LOM[i] := HIQH[i] := Л end; (* установлены начальные значения параметров отрезков *) (* распределение точек по отрезкам *) for i := 1 until N — 1 do
begin BUCKET := 1 + l(N - 1) X (X[i\ -MIN)/(MAX-MIN)J;
COUNT[BUCKET] := COUNT [BUCKET] + 1; LOW[BUCKET] := min(Vfl, LOW[BUCKET]); 2) HIGH[BUCKET] := max (X[i], HIGH[BUCKET]); 2)
end;
(* Заметим, что ЛГ —2 точек распределены по N— I отрезкам, и, следовательно, один из отрезков должен быть пустым. Это значит, что наибольший промежуток не может помещаться между двумя точками, попавшими в один и тот же отрезок. Теперь достаточно выполнить однократный просмотр отрезков *) MAXGAP := 0; LEFT := HIGH[1];
') MIN и MAX присваиваются значения соответственно минимального и максимального элементов массива X. — Прим. перев. ') Здесь считается, что min (*, Л) = max (*, Л) = х.
320
Гл. 6. Близость: варианты и обобщения
for i := 2 until N — 1 do if (COUNT[i] ф 0) then
begin THISGAP := LOW[(] - LEFT; MAXGAP := max(THISGAP, MAXGAP); LEFT := НЮНИ end
end.
Этот алгоритм несколько проливает свет на вычислительную мощность функции выделения целой части. Учитывая кажущееся сходство задач МАКСИМАЛЬНЫЙ ПРОМЕЖУТОК и БЛИЖАЙШАЯ ПАРА в одномерном случае, существование алгоритма с линейной сложностью представляет выдающийся результат. К сожалению, по-видимому, невозможно обобщить этот результат на случай двумерного пространства.
6.5. Замечания и комментарии
Хотя евклидово минимальное остовное дерево множества точек на плоскости может быть построено за оптимальное время, построение ЕМОД в пространствах более высокой размерности, вообще говоря, остается открытой задачей. Используя геометрическую природу задачи, Яо [Yao (1982)] разработал алгоритм построения ЕМОД множества из N точек в d-мерном пространстве за время Т (N, d) = О (N2-a<-d) • ¦ (\ogN)l~aW), где a (d) = 2~'d+1), имеющий оценку 0(N(logN)]'b) для d — Ъ (этот метод тесно связан с алгоритмом Яо для определения диаметра множества точек (см. разд. 4.3)).
С диаграммой Вороного тесно связана задача построения скелета многоугольника, являющегося предметом довольно большого числа исследований, относящихся к распознаванию образов, так как он довольно хорошо отражает «форму» многоугольника. Скелет простого многоугольника Р — это множество а его внутренних точек таких, что каждая точка pea равноудалена по крайней мере от двух точек на границе Р. В связи с этим скелет многоугольника также называют срединными осями [Duda, Hart (1973)]. Образование скелета многоугольника можно наглядно представить, наблюдая процесс «выгорания» многоугольника. Представьте, что по всей границе многоугольника одновременно загорается огонь. Если предположить, что огонь распространяется с постоянной скоростью, то точки, в которых происходит встреча фронтов распространения огня, образуют скелет многоугольника (этот процесс ассоциируется с пожаром в прерии). В другой интерпретации скелет — это подграф планарной карты, образованной областями близости
