Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Проведенный анализ позволил установить сводимость задач, представленную на рис. 5.6. Учитывая, что в рамках модели деревьев вычислений обе задачи ЕДИНСТВЕННОСТЬ ЭЛЕМЕНТОВ и СОРТИРОВКА — на множестве из N элементов имеют нижнюю оценку сложности Q(N\ogN), имеет место следующая теорема.
Теорема 5.2. В рамках модели деревьев вычислений любой алгоритм, решающий одну из задач — БЛИЖАЙШАЯ ПАРА,
•) Эквивалентное сведение — УПОРЯДОЧЕННАЯ ОБОЛОЧКА сс^ ТРИАНГУЛЯЦИЯ — основывается на том, что триангуляция множества S является планарным графом (уложенным на плоскости), внешняя граница которого является выпуклой оболочкой множества S.
238
Гл. 5. Близость: основные алгоритмы
ВСЕ БЛИЖАЙШИЕ СОСЕДИ, ЕМОД, ТРИАНГУЛЯЦИЯ,— требует Q (N log N) операций.
В последующих разделах мы займемся исследованием алгоритмов решения этих задач, стараясь найти оптимальные алгоритмы.
5.4. Решение задачи о ближайшей паре методом «разделяй и властвуй»
Нижняя оценка, даваемая теоремой 5.2, стимулирует нас на поиск алгоритма, решающего задачу БЛИЖАЙШАЯ ПАРА и имеющего сложность Q{N\ogN). Для достижения этой цели представляются разумными два пути, которые и стоит попробовать: непосредственное использование сортировки и применение метода «разделяй и властвуй». Можно сразу
Рис. 5.8. Пример, показывающий неприменимость метода, основанного на проецировании. Точки рх и р2, образующие ближайшую пару, имеют наибольшее расстояние по (/-координате.
же отвергнуть первый поход, так как сортировка оказывается полезной лишь в условиях наличия полной упорядоченности. Единственный разумный способ получить полное упорядочение заключается, по-видимому, в проецировании всех точек на некоторую прямую. Но, к сожалению, при проецировании теряется существенная в данном случае информация. Это демонстрирует рис. 5.8, на котором точки р\ и р2 образуют ближайшую пару, но при этом дают максимальное расстояние при проецировании на ось у.
Второй путь к достижению сложности Q(NlogN) заключается в разбиении задачи на две подзадачи, решения которых можно объединить за линейное время, получая решение исходной задачи [Bentley, Shamos (1976); Shamos (1980)]. Непосредственное применение метода «разделяй и властвуй» в данном случае не принесет успеха, и довольно поучительно разобраться в причинах неудачи. Хорошо было бы разбить множество на два подмножества Si и S2 по Л7/2 точек в каждом и рекурсивно найти в каждом из них ближайшую пару точек. Но возникает вопрос:
5.4. Решение задачи о ближайшей паре
239
как использовать полученную информацию? Не исключена возможность, что одна из точек, образующих ближайшую пару, принадлежит подмножеству Si, а вторая — S2. При этом не видно способа, позволяющего избежать N2/4 дополнительных сравнений. Обозначим через P(N, 2) время работы алгоритма, ищущего ближайшую пару точек на плоскости. Предыдущие рассуждения дают следующее рекуррентное соотношение: P(N, 2) = 2P(N/2, 2) + 0(N2).
Решением этого соотношения является P(N, 2)= 0(N2). Попытаемся внести некоторые изменения, чтобы преодолеть возникшее затруднение. Для этого рассмотрим одномерный случай.
В одномерном случае известен лишь единственный алгоритм, решающий эту задачу и имеющий сложность Q(N log N). Этот
S, 5г_
Pi Рг Рз | Чз Ъ <fe
тп
Рис. 5.9. Метод «разделяй и властвуй» в одномерном случае.
алгоритм упорядочивает точки множества, а затем просматривает его за линейное время. Поскольку, как уже отмечалось выше, сортировка не допускает обобщения на двумерный случай, попытаемся разработать для одномерного случая метод типа «разделяй и властвуй», допускающий обобщение на двумерный случай. Предположим, что точка m разбивает множество на два подмножества Si и S2 и при этом р < q для всех р е Si и q е S2. Решив раздельно рекурсивным образом задачу о ближайшей паре для множеств Sj и S2, получим две пары точек {р\, рг} и {qi,q2}, представляющие ближайшие пары для Si и S2 соответственно. Обозначим б наименьшее расстояние, найденное на текущий момент (рис. 5.9): б = min(|р2 — pi 1, \q2 — qi\).
Ближайшей парой во всем множестве является либо {pi, р2}, либо {qi,q2}, либо {р3, q3}, где р3 g Sb ?3е52. Обратим внимание на следующий ключевой момент: для того чтобы расстояние, даваемое парой {р3, q3], было меньше б, р3 и q3 должны находиться на расстоянии, не превышающем б от точки т. (Ясно, что р3 должна быть самой правой точкой множества Sb а ?з — самой левой точкой множества S2, но такая характеристика точек не имеет особого смысла в пространствах более высокой размерности, и поэтому мы предпочли нечто более об-
240
Гл. 5. Близость: основные алгоритмы
щее.) Сколько точек множества Si могут находиться в интервале (пг — б, пг]? Так как каждый полуоткрытый интервал длиной б содержит не более одной точки множества Si, то интервал (т — б, т] содержит не более одной точки. Аналогично интервал [т, т + б) содержит самое большее одну точку. Таким образом, число сравнений, которые необходимо сделать для точек, выбираемых из различных подмножеств, не превышает одного. Очевидно, что все точки, попадающие в интервалы (т — б, т] и [т, m-f-б), можно определить, просмотрев множество за линейное время. Таким образом, получаем следующий алгоритм, имеющий сложность O(NlogN): function BnAPAl(S)
