h1. Minimal enclosing circle
(Categoria _Geometrie analitica_, Autor _Bogdan Tataroiu_)
(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. 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. )
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 {$π$}. 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 ( 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^)$}.
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^)$}.
h2. Algoritm {$O(N)$}
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
... TODO search net .. something random and nice
h2. Istoria problemei
