h1. Minimal enclosing circle
(Autor Bogdan Tataroiu)
(Categoria _Geometrie analitica_, Autor _Bogdan Tataroiu_)
In cadrul acestui articol vom analiza problema determinarii unui cerc de raza minima ce contine in interior sau pe circumferinta toate punctele dintr-un set dat. Aceasta problema mai poate fi gasita si sub denumirea de _Smallest Enclosing Circle_ sau _Mininum Spanning Circle_.
# Se construieste un cerc de raza suficient de mare incat sa cuprinda toate punctele in mod sigur (raza infinit) si un centru ales aleator.
# 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.
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. Acest lucru se poate implementa printr-o parcurgere a punctelor din set. Pentru fiecare punct {$B$} din set se calculeaza raza cercului astfel incat centrul cercului sa ramana pe aceeasi axa fata de puncutl {$A$} si {$B$} sa se afle pe cerc ( se formeaza un triunghi isoscel, care are ca baza segmentul AB si celelalte muchii egale cu raza. Se poate calcula raza cercului folosind teorema cosinusului. )
# 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 {$π$}, 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^)$}.
Algoritmul este destul de usor de vizualizat, dar destul de dificil de implementat ( trebuie cateva cunostinte de geometrie ). 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^)$}.
h2. Algoritm {$O(N)$}
... TODO search net .. something random and nice
Algoritmul acesta construieste cercul in mod incremental, adaugand pe rand puncte in cercul de raza minima.
Pentru inceput, se permuta punctele din set intr-un mod aleator si se formeaza un cerc care are ca diametru segmentul format de primele 2 puncte din permutare. Notam cu R(i) raza minima pentru .. TODO
h2. Istoria problemei
