Revizia anterioară Revizia următoare
Minimal enclosing circle
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.
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. 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 considera cercurile determinate de fiecare pereche de puncte din set, cu diametrul egal cu segmentul ce uneste cele 2 puncte, alaturi de cele determinate de oricare 3 puncte din set.
- Se verifica care dintre acestea contin in interior toate punctele din set si se alege cel de raza minima.
Algoritmul descris are complexitate O(N3) pentru generarea cercurilor si inca O(N) pentru fiecare cerc pentru verificare, in total avand O(N4).
Algoritm O(N2) 
... TODO de scris...
Algoritm O(N)
... TODO search net .. something random and nice
Istoria problemei
... TODO.. non-important.. may be removed in final form :P
Exercitii: SPOJ ALIENS
