Близькість, Детальна інформація

r

t

x

z

|

\x0160

\x0152

\x017D

’

”

O

U

a

, що точки p3 та q3 повинні знаходитися на відстані, яка не перевищує \xF064 від точки m).

Blpara (S, Begin, End)

if Begin = End then return MAXINT;

if (Begin - End) = 1 then return S[End] - S[Begin];

Mediana = (Begin + End) / 2;

ResS1 = blpara(Begin, Mediana);

ResS2 = blpara(Mediana + 1, End);

Delta = S[Mediana + 1] - S[Mediana ];

return min (ResS1, ResS2, Delta);

Двовимірний випадок. Алгоритм розділяй та пануй.

Розіб’ємо множину S на дві підмножини S1 та S2 так, щоб кожна точка S1 лежала лівіше довільної точки S2. Тобто множина точок розбивається на частини вертикальною прямою l, що визначається медіаною множини S по x координаті. Розв’язавши задачу для S1 та S2, отримаємо числа \xF064\xF031 та \xF064\xF032\xF020– мінімальні відстані для множин S1 та S2 відповідно. Покладемо \xF064 = min (\xF064\xF031, \xF064\xF032).

Якщо найближчу пару утворюють точки p \xF0CE\xF020S1 та q \xF0CE\xF020S2, то відстані від p та q до l не перевищують \xF064. Позначимо через P1 та P2 дві вертикальні смуги шириною \xF064, розташовані відповідно зліва та справа від l. Тоді p \xF0CE P1 та q \xF0CE\xF020P2. Ми повинні знайти всі точки q \xF0CE\xF020P2, віддалені від p не більш ніж на \xF064. Всі такі точки повинні знаходитися в прямокутнику R розміром \xF064\xF020\xF0B4\xF0202\xF064. Відомо, що жодна пара точок в P2 не знаходиться на відстані, меншій за \xF064. Максимальна кількість точок, яку можна розмістити в такому прямокутнику, дорівнює 6. Оже для кожної точки з P1 необхідно дослідити не більше шести точок з P2. На кроці злиття розв’язків підзадач необхідно виконати не більш ніж 6 * N/2 = 3N порівнянь.

1. Розбити S на дві підмножини S1 та S2 вертикальною прямою l, яка ділить множину S навпіл.

2. Рекурсивно знайти відстані для найближчих пар \xF064\xF031 та \xF064\xF032.

3. \xF064 = min (\xF064\xF031, \xF064\xF032).

4. Нехай P1 – множина точок з S1, що лежать в смузі на віддалені \xF064 від розділяючої прямої l, а P2 – аналогічна підмножина в S2. Спроеціювати P1 та P2 на l та впорядкувати проекції за y координатою. Нехай P1* та P2* – відповідні впорядковані послідовності.

5. Злиття можна виконати, переглядаючи P1* і для кожної точки з P1* досліджувати точки з P2*, що знаходяться на відстані не більшій за \xF064. Нехай \xF064l – найменша відстань між парою точок, знайдена в ході виконання процедури злиття.