Problem najbližjega para točk

Najbližji par točk označen z rdečo barvo

Problem najbližjega para točk je znan problem iz računalniške geometrije, pri katerem imamo podano množico točk, naša naloga pa je poiskati tisti dve točki, ki sta si najbližji.

Za rešitev lahko izračunamo razdalje med vsemi pari točk, nato pa izberemo najkrajši par. Ta pristop mora pri množici velikosti n obdelati $n*(n-1)/2$ parov točk in ima tako časovno zahtevnost $O(n^2)$.

Mejnik v računalniški geometriji je bil algoritem za rešitev problema najbližjega para točk, ki uporablja strategijo deli in vladaj in ima časovno zahtevnost $O(n\log n)$.