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

Розіб’ємо множину 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 – найменша відстань між парою точок, знайдена в ході виконання процедури злиття.

6. \xF064S = min (\xF064, \xF064l).

Теорема. Найкоротша відстань, яка визначається N точками на площині, може бути знайдена за час O(N * log N), який є оптимальним.

q3

q2

q1

p3

p2

p1

m

\xF064

\xF064

\xF064\xF031

P\xF032

l

S\xF032

S\xF031

P\xF031

\xF064\xF032