În continuare vom descrie un algoritm 'divide şi stăpâneşte':http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm al cărui timp de execuţie este $O(n log{~2~}(n))$.

Considerăm $P$ mulţimea tuturor punctelor date. În cazul în care $|P| &le; 3$ se vor considera toate cele <tex> \binom{|P|}{2} </tex> perechi de puncte şi se reţine perechea cea mai apropiată. Dacă $|P| &gt; 3$, se va folosi paradigma divide şi stăpâneşte după cum urmează...

Considerăm $P$ o submulţime a punctelor date. Iniţial, $P$ va conţine toate punctele. În cazul în care $|P| &le; 3$ se vor considera toate cele <tex> \binom{|P|}{2} </tex> perechi de puncte şi se reţine perechea cea mai apropiată. Dacă $|P| &gt; 3$, se va folosi paradigma divide şi stăpâneşte după cum urmează...

# _divide:_ determină o dreaptă verticală $d$ care împarte mulţimea $P$, menţionată mai sus, în două submulţimi $P{~s~}$ şi $P{~d~}$, astfel încât $||P{~s~}| - |P{~d~}|| ≤ 1$, adică numărul punctelor din cele două mulţimi diferă cu cel mult unu. Punctele din $P{~s~}$ se găsesc în stânga dreptei verticale $d$ iar cele din $P{~d~}$ în dreapta.
# _stăpâneşte:_ se fac două apeluri recursive, unul pentru a determina cea mai apropiată pereche de puncte din $P{~s~}$, şi celălalt pentru a determina cea mai apropiată pereche de puncte din $P{~d~}$. Fie $§{~s~}$ şi $§{~d~}$ valorile returnate şi fie $§ = min(§{~s~}, §{~d~})$.

Depinzând de implementare, există soluţie de complexitate $O(n log{~2~}^2^(n))$ şi soluţie de complexitate $O(n log{~2~}(n))$. Soluţia din urmă presupune ca la revenirea din apelul recursiv, cele două submulţimi de puncte sortate după ordonată să fie interclasate în timp liniar şi nu sortate.

*Marius* 1. Mai multe detalii la implementare 2. Două desene 3. Schimbate teste pentru ca sursa în log^2^ să ia 70 şi nu doar 40.

*Marius* 1. Mai multe detalii la implementare 2. Două desene

h2. Aplicaţii