Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Входные данные: X[l: N], N точек множества S в одномерном пространстве.
Выходные данные: б — расстояние между ближайшей парой точек.
begin if (|S| = 2)then б := \Х[2] - Х[1] | else if(|S| = 1) then б := со
else begin т := Медиана(5);
Построить(5, ,S2) (* Si = [p : p < m}, S2 = {p:p>m} *); 6, := BnAPAl(Si); 62:=BnAPAl(S2); p := max(Si); q := min(S2); б := min(6] ,62,q — p)
end; return б
end.
Хотя этот алгоритм, очевидно, сложнее алгоритма, использующего сортировку с последующим просмотром, но он обеспечивает искомый переход к двумерному случаю.
Обобщение на двумерный случай можно выполнить самым непосредственным способом. Разобьем множество точек на плоскости S на два подмножества S( и S2 так, чтобы каждая точка Si лежала левее любой точки S2. То есть множество разбивается на части вертикальной прямой определяемой медианой множества S по я-координате. Решив рекурсивно задачу для Si и S2, получим числа 6i и бг — минимальные расстояния для множеств Si и S2 соответственно. Положим б = min(6i, б2). (См. рис. 5.10.)
Если ближайшую пару образуют точки peS; и ?gS2, то, очевидно, расстояния от р и q до / не превышают б. Таким образом, если обозначить через Pi и Р2 две вертикальные полосы
5.4. Решение задачи о ближайшей паре
241
шириной б, расположенные соответственно слева и справа от /, то реР, и q е Р2. Здесь возникает затруднение, которого не было в одномерном случае. На прямой было не более одного
Pi рг
Рис. 5.10. Метод «разделяй и властвуй» в случае плоскости.
кандидата ') для р и q. На плоскости таким кандидатом может быть любая точка, если она находится на расстоянии, не превышающем б, от прямой /. На рис. 5.11 приведен пример такого
множества. Может показаться, что для определения ближайшей пары вновь потребуется выполнить N2/4 сравнений расстояний между точками. Но мы сейчас покажем, что в действительности
') В процедуре БПАРА1 имеется в точности один кандидат для р: р = = inaxfS,).
242
Гл. 5. Близость: основные алгоритмы
точки, попадающие в полосы шириной 6, расположенные по обе стороны от прямой /, обладают особой структурой.
Обращаясь к рис. 5.12, рассмотрим в полосе Pi произвольную точку р. Мы должны найти все точки q в Р2, удаленные от р не более чем на б. Но сколько может быть таких точек? Все они должны находиться в прямоугольнике R размером б X 26. Кроме того, известно, что никакая пара точек в Р2 не может находиться на расстоянии, меньшем б друг от друга1). Как показано на рисунке, максимальное число точек, которые можно поместить в такой прямоугольник так, чтобы расстояние между ними было не меньше б, равно шести. Это значит, что для каждой точки из Pi необходимо исследовать лишь не более шести точек из Р2, а вовсе не N/2 точек. Следовательно, на шаге слияния решений подзадач нужно выполнить не более 6 X N12 = 3N сравнений расстояний вместо N2/4.
Но пока мы еще не получили алгоритм со сложностью 0(N log N), так как хотя и известно, что для каждой точки из Pi необходимо исследовать лишь шесть точек из Р2, но не известно, какие именно точки нужно исследовать! Чтобы ответить на этот вопрос, предположим, что точка р и все точки из Р2 спроецированы на прямую /. Для определения точек из Р2, попадающих в R, можно рассмотреть лишь проекции точек, находящихся на расстоянии не более б от проекции точки р (их не более шести). Если точки упорядочены по «/-координате, то для всех точек из Pi «кандидаты» на место их ближайшего соседа из Р2 могут быть найдены за один проход этого упорядоченного списка. Ниже дан набросок алгоритма в том виде, как он разработан на данный момент.
procedure BnAPA2(S)
1. Разбить 5 на два подмножества S{ и S2 вертикальной прямой /, делящей множество пополам.
2. Рекурсивно найти расстояния для ближайших пар 61 и б2.
3. 6:=min(6i,62).
4. Пусть Pi — множество точек из 5Ь лежащих в полосе на удалении б от разделяющей прямой /, а Р2 — аналогичное подмножество в 52. Спроецировать Р\ и Р2 на / и упорядочить проекции по «/-координате. Пусть Р* и Р* — соответствующие упорядоченные последовательности.
5. «Слияние» можно выполнить, просматривая Р* и для каждой точки из Р\, изучая точки из Р2, находящиеся на расстоянии, не превышающем б. Пока указатель продвигается по последовательности Р*, указатель на Р\ может перемещаться
') Это принципиальное соображение принадлежит Стронгу (частное сообщение, 1974).
5.4. Решение задачи о ближайшей паре
243
вперед-назад, оставаясь в интервале шириной 26. Пусть б; — минимальное расстояние между парой точек, найденное в ходе этой процедуры.
6. 6S :== min(6, 6г).
Если обозначить через T(N) время обработки алгоритмом множества из N точек, то время, затрачиваемое на обработку на шагах 1 и 5, равно O(N), на шагах 3 и 6 затрачивается постоянное время, а шаг 2 требует времени 2T(N/2). Если бы сортировку нужно было производить при каждом выполнении шага 4, то на это требовалось бы время О (N log N). Однако можно прибегнуть к стандартному приему, называемому предварительной сортировкой, когда один раз создается упорядоченный по ^/-координате список всех точек, а затем при выполнении шага 4 из этого списка за время O(N) выделяются в упорядоченном виде необходимые точки1). Эта небольшая хитрость позволяет записать для времени обработки P(N, 2) алгоритма поиска ближайшей пары в двумерном случае следующее рекуррентное соотношение:
