Близькість
Задача. Найближча пара. На площині задано N точок. Знайти дві з них, відстань між якими найменша.
В одномірному випадку можна впорядкувати координати точок за час O(N * log N) а потім за лінійний час проглянути точки x1, x2, ..., xN обчислюючи значення xi+1 - xi, i = 1, ..., N-1.
Означення. Точа b є найближчим сусідом точки a множини S (позначається a ??b), якщо
dist(a, b) = min dist(a, c), c ??S / a.

Відношення найближчий сусід на множині точок
Задача. Єдиність елементів. Дано N дійсних чисел. Чи є серед них два рівних числа?
Теорема. Задача єдиність елементів лінійно зводиться до задачі найближча пара.
Доведення. Дано множину дійсних чисел {x1, x2, ..., xN}. Розглядаємо їх як точки на прямій y = 0 та намагаємося знайти найближчу пару точок. Якщо відстань між найближчою парою точок не дорівнює нулю, то усі числа різні.
Задача. Найближчі сусіди. На площині задано N точок. Знайти найближчого сусіда для кожної точки множини.
Задача. Евклідове мінімальне остове дерево (ЕМОД). На площині задано N точок. Побудувати дерево, вершинами якого є всі задані точки і сумарна довжина всіх ребер якого мінімальна.

Теорема. Задача сортування за лінійний час зводиться до задачі ЕМОД.
Доведення. Розглянемо кожне число xi множини {x1, x2, ..., xN} як точку (xi, 0) на площині та будуємо ЕМОД. В побудованому дереві вершини, які відповідають числам xi та xj, сполучені ребром тоді і тільки тоді, коли утворюють пару послідовних чисел у впорядкованій множині. Розв’язком задачі ЕМОД є список з N - 1 пар (i, j), кожна з яких визначає ребро дерева. Цей список можна впорядкувати за лінійний час.
Задача. Триангуляція. На площині задано N точок. Сполучити їх неперетинаючими відрізками так, щоб кожна область всередині опуклої оболонки цієї множини точок була трикутником.
Теорема. Задача сортування за лінійний час зводиться до задачі триангуляції.
Доведення. Розташуємо N-1 точку з множини {x1, x2, ..., xN} на одній прямій, а одну точку не на прямій. Триангуляція множини точок може бути проведена єдиним чином:
Список ребер, що породжується алгоритмом триангуляції, можна використати для отримання впорядкованого списку чисел xi за час O(N)
Найближча пара
Одномірний випадок. Алгоритм розділяй та пануй.
q3
q2
q1
p3
p2
p1
m
Припустимо, що точка m розбиває множину S на дві підмножини S1 та S2, при чому p < q для всіх p ??S1 та q ??S2. Рекурсивним чином розв’язуємо задачу про найближчу пару для множин S1 та S2 і отримаємо дві пари точок {p1, p2} та {q1, q2}, які представляють найближчі пари для S1 та S2 відповідно. Позначимо через ??найменшу відстань, знайдену на поточний момент: ??= min( |p2 - p1|, |q2 - q1|). Найближчою парою у множині S буде або {p1, p2}, або {q1, q2}, або {p3, q3}, де p3 – права точка множини S1, а q3 – ліва точка множини S2 (це випливає з того, що точки p3 та q3 повинні знаходитися на відстані, яка не перевищує ? від точки 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, отримаємо числа ?? та ???– мінімальні відстані для множин S1 та S2 відповідно. Покладемо ? = min (??, ??).
?
?
??
P?
l
S?
S?
P?
??

Якщо найближчу пару утворюють точки p ??S1 та q ??S2, то відстані від p та q до l не перевищують ?. Позначимо через P1 та P2 дві вертикальні смуги шириною ?, розташовані відповідно зліва та справа від l. Тоді p ? P1 та q ??P2. Ми повинні знайти всі точки q ??P2, віддалені від p не більш ніж на ?. Всі такі точки повинні знаходитися в прямокутнику R розміром ????2?. Відомо, що жодна пара точок в P2 не знаходиться на відстані, меншій за ?. Максимальна кількість точок, яку можна розмістити в такому прямокутнику, дорівнює 6. Оже для кожної точки з P1 необхідно дослідити не більше шести точок з P2. На кроці злиття розв’язків підзадач необхідно виконати не більш ніж 6 * N/2 = 3N порівнянь.
1. Розбити S на дві підмножини S1 та S2 вертикальною прямою l, яка ділить множину S навпіл.
2. Рекурсивно знайти відстані для найближчих пар ?? та ??.
3. ? = min (??, ??).
4. Нехай P1 – множина точок з S1, що лежать в смузі на віддалені ? від розділяючої прямої l, а P2 – аналогічна підмножина в S2. Спроеціювати P1 та P2 на l та впорядкувати проекції за y координатою. Нехай P1* та P2* – відповідні впорядковані послідовності.
5. Злиття можна виконати, переглядаючи P1* і для кожної точки з P1* досліджувати точки з P2*, що знаходяться на відстані не більшій за ?. Нехай ?l – найменша відстань між парою точок, знайдена в ході виконання процедури злиття.
6. ?S = min (?, ?l).
Теорема. Найкоротша відстань, яка визначається N точками на площині, може бути знайдена за час O(N * log N), який є оптимальним.