Problem najbližjega para točk

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.

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

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 parov točk in ima tako časovno zahtevnost .

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 .