h2. Algoritm naiv

Este clar ca cercul de raza minima ce include toate punctele din setul dat trebuie sa aiba pe circumferinta cel putin 2 puncte, altfel am putea micsora raza cercului pana cand am atinge si al doilea punct. Daca pe cerc exista 2 puncte consecutive ce formeaza un arc de cerc mai mare de Pi, atunci cercul poate fi micsorat, ducand centrul cercului inspre segmentul format de cele 2 puncte. Astfel, singurul caz in care cercul de raza minima contine doar 2 puncte pe circumferinta este atunci cand diametrul cercului este egal cu segmentul ce uneste cele 2 puncte, in celelalte cazuri cercul este determinat de 3 (sau posibil mai multe puncte) din set.

Este clar ca cercul de raza minima ce include toate punctele din setul dat trebuie sa aiba pe circumferinta cel putin 2 puncte, altfel am putea micsora raza cercului pana cand am atinge si al doilea punct. Daca pe cerc exista 2 puncte consecutive ce formeaza un arc de cerc mai mare de {$&pi$};, atunci cercul poate fi micsorat, ducand centrul cercului inspre segmentul format de cele 2 puncte. Astfel, singurul caz in care cercul de raza minima contine doar 2 puncte pe circumferinta este atunci cand diametrul cercului este egal cu segmentul ce uneste cele 2 puncte, in celelalte cazuri cercul este determinat de 3 (sau posibil mai multe puncte) din set.

De aici este destul de usor de formulat un algoritm:

# Se gaseste punctul cel mai departat de centrul cercului, notat cu {$A$}, si se micsoreaza raza cercului pana cand acesta atinge punctul.
Practic raza cercului devine egala cu distanta dintre punctul {$A$} si centrul ales
# In cazul in care cercul trece deja prin 2 sau mai multe puncte trecem la pasul numarul 4. In caz contrar, se apropie centrul cercului de punctul {$A$}, determinat la punctul 2, pana cand cercul intersecteaza un nou punct.

# In acest moment avem un cerc determinat de cel putin 2 puncte. Dupa cum am zis mai sus, un cerc de raza minima nu trebuie sa contina 2 puncte consecutive ce formeaza un arc de cerc mai mare de Pi. Daca cercul nostru nu contine un astfel de arc de cerc, atunci am determinat cercul de raza minima pentru setul de puncte. In caz contrar, notam cu {$D$} si {$E$} aceste 2 puncte. Pentru a micsora lungimea arcului dintre cele doua puncte, translatam centrul cercului pe directia perpendiculara cu segmentul {$DE$}, inspre acest segment pana cand:

# In acest moment avem un cerc determinat de cel putin 2 puncte. Dupa cum am zis mai sus, un cerc de raza minima nu trebuie sa contina 2 puncte consecutive ce formeaza un arc de cerc mai mare de {$π$}. Daca cercul nostru nu contine un astfel de arc de cerc, atunci am determinat cercul de raza minima pentru setul de puncte. In caz contrar, notam cu {$D$} si {$E$} aceste 2 puncte. Pentru a micsora lungimea arcului dintre cele doua puncte, translatam centrul cercului pe directia perpendiculara cu segmentul {$DE$}, inspre acest segment pana cand:

## centrul cercului ajunge pe segmentul {$DE$}. In acest moment {$DE$} a devenit diametru in cerc si am determinat cercul de raza minima

## cercul intalneste un alt punct {$F$}. Daca mai exista 2 puncte consecutive pe cerc care se formeaza un arc de cerc cu lungime mai mare de Pi, atunci trebuie sa repetam pasul 4. In caz contrar, am ajuns la solutie.

## cercul intalneste un alt punct {$F$}. Daca mai exista 2 puncte consecutive pe cerc care se formeaza un arc de cerc cu lungime mai mare de {$π$}, atunci trebuie sa repetam pasul 4. In caz contrar, am ajuns la solutie.

Algoritmul este destul de usor de vizualizat, dar destul de dificil de implementat. Fiecare pas din algoritm are complexitate {$O(N)$}, dar pasul 4 poate fi repetat de maxim {$N - 2$} ori, ceea ce duce in final la o complexitate {$O(N^2^)$}.