Notam cu {$C{~I~}$} cercul de raza minima ce contine in interior punctele din setul {$I$}.

Pentru fiecare punct {$P$}, putem determina in timp constant daca punctul se afla in interiorului cercului {$C{~I~}$}. In cazul in care {$P$} este inclus in {$C{~I~}$}, atunci {$C{~I+{P}~}$} va fi egal cu {$C{~I~}$}. In caz contrar, trebuie sa schimbam cercul {$C{~I~}$} pentru a cuprinde si acest punct. Cercul ce cuprinde toate punctele va fi evident {$C{~S~}$}, unde {$S$} este setul de puncte dat. Singura problema este cum determinam acel cerc modificat.

Pentru fiecare punct {$P$}, putem determina in timp constant daca punctul se afla in interiorului cercului {$C{~I~}$}. In cazul in care {$P$} este inclus in {$C{~I~}$}, atunci {$C{~I U {P}~}$} va fi egal cu {$C{~I~}$}. In caz contrar, trebuie sa schimbam cercul {$C{~I~}$} pentru a cuprinde si acest punct. Cercul ce cuprinde toate punctele va fi evident {$C{~S~}$}, unde {$S$} este setul de puncte dat. Singura problema este cum determinam acel cerc modificat.

Vom demonstra in continuare ca daca punctul {$P$} se afla in exteriorul cercului {$C{~I~}$}, atunci el trebuie sa fie pe circumferinta cercului {$C{~I+{P}~}$}.

Vom demonstra in continuare ca daca punctul {$P$} se afla in exteriorul cercului {$C{~I~}$}, atunci el trebuie sa fie pe circumferinta cercului {$C{~I U {P}~}$}.

* {!>minimum-enclosing-circle?arccerc.png 75%!} Dandu-se doua cercuri de raza {$R{~1~}$} si {$R{~2~}$}, avand {$R{~1~} < R{~2~}$}, atunci intersectia cercului de raza {$R{~2~}$} cu interiorul cercului de raza {$R{~1~}$} formeaza un arc de cerc de lungime mai mica decat {$&pi;$} (cel albastru in poza alaturata). Daca arcul de cerc ar avea o lungime mai mare ca {$&pi;$} atunci acesta ar trebui sa contina 2 puncte diametral opuse, aflate la o distanta de {$2R{~2~}$}, insa in cercul de raza {$R{~1~}$} cea mai mare distanta intre 2 puncte din interiorul sau poate fi maxim {$2R{~1~}$}. Cum {$R{~1~} < R{~2~}$}, acest lucru este imposibil.

* Presupunem prin reducere la absurd ca {$P$} nu apartine circumferintei cercului {$C{~I+{P}~}$}. Este usor de vazut ca raza cercului {$C{~I~}$} este mai mica ca cea a cercului {$C{~I+{P}~}$}, deoarece {$C{~I+{P}~}$} cuprinde un punct care nu este cuprins de {$C{~I~}$}. Daca notam cu {$R{~1~}$} raza cercului {$C{~I~}$} si cu {$R{~2~}$} raza cercului {$C{~I+{P}~}$}, atunci intersectia cercului {$C{~I+{P}~}$} cu interiorul cercului {$C{~I~}$} este un arc de cerc de lungime mai mica ca {$π$}.
* Datorita faptului ca {$P$} nu apartine circumferintei cercului {$C{~I+{P}~}$}, punctele care definesc cercul {$C{~I+{P}~}$} se afla printre punctele din setul {$I$}. Cum toate aceste puncte se afla in interiorul cercului {$C{~I~}$} si intersectia cercului {$C{~I+{P}~}$} cu interiorul cercului {$C{~I~}$} este un arc de cerc de lungime mai mica decat {$π$}, punctele care determina cercul {$C{~I+{P}~}$} trebuie sa se afle pe acest arc de cerc. Astfel avem cel putin 2 puncte consecutive pe circumferinta cercului {$C{~I+{P}~}$} care formeaza un arc de cerc de lungime mai mare {$π$} (cel albastru in rosu alaturata).
* Acest lucru intra in contradictie cu faptul ca cercul are raza minima. Astfel {$P$} trebuie sa se afle pe circumferinta cercului {$C{~I+{P}~}$}.

* Presupunem prin reducere la absurd ca {$P$} nu apartine circumferintei cercului {$C{~I U {P}~}$}. Este usor de vazut ca raza cercului {$C{~I~}$} este mai mica ca cea a cercului {$C{~I U {P}~}$}, deoarece {$C{~I U {P}~}$} cuprinde un punct care nu este cuprins de {$C{~I~}$}. Daca notam cu {$R{~1~}$} raza cercului {$C{~I~}$} si cu {$R{~2~}$} raza cercului {$C{~I U {P}~}$}, atunci intersectia cercului {$C{~I U {P}~}$} cu interiorul cercului {$C{~I~}$} este un arc de cerc de lungime mai mica ca {$π$}.
* Datorita faptului ca {$P$} nu apartine circumferintei cercului {$C{~I U {P}~}$}, punctele care definesc cercul {$C{~I U {P}~}$} se afla printre punctele din setul {$I$}. Cum toate aceste puncte se afla in interiorul cercului {$C{~I~}$} si intersectia cercului {$C{~I U {P}~}$} cu interiorul cercului {$C{~I~}$} este un arc de cerc de lungime mai mica decat {$π$}, punctele care determina cercul {$C{~I U {P}~}$} trebuie sa se afle pe acest arc de cerc. Astfel avem cel putin 2 puncte consecutive pe circumferinta cercului {$C{~I U {P}~}$} care formeaza un arc de cerc de lungime mai mare {$π$} (cel albastru in rosu alaturata).
* Acest lucru intra in contradictie cu faptul ca cercul are raza minima. Astfel {$P$} trebuie sa se afle pe circumferinta cercului {$C{~I U {P}~}$}.

Acum trebuie doar sa calculam cel mai mic cerc care contine punctele din setul I in interior si care are punctul {$P$} pe circumferinta. Vom extinde {$C{~I~}$} adaugand un nou parametru. Astfel notam cu {$C{~I,B~}$} cercul de raza minima ce contine setul {$I$} de puncte in interior si punctele din setul {$B$} pe circumferinta (pot exista si alte puncte pe circumferinta, dar cele din setul {$B$} sunt fortate). Cercul de raza minima care contine toate punctele va fi {$C{~S,{}~}$}.

Calcularea lui {$C{~I,B~}$} se face in mod recursiv. Daca {$B$} are cel putin 3 puncte atunci {$C{~I,B~}$} devine cercul determinat de acestea. In caz contrar se alege un punct random (notat cu {$P$}) din setul {$I$}. In cazul in care punctul {$P$} se afla in interiorul cercului {$C{~I-{P},B~}$}, atunci cercul acesta nu mai trebuie marit si {$C{~I,B~}$} devine egal cu {$C{~I-{P},B~}$}. In cazul in care punctul {$P$} nu se afla in interiorul acelui cerc {$C{~I,B~}$} devine egal cu {$C{~I-{P},B+{P}~}$}.

Calcularea lui {$C{~I,B~}$} se face in mod recursiv. Daca {$B$} are cel putin 3 puncte atunci {$C{~I,B~}$} devine cercul determinat de acestea. In caz contrar se alege un punct random (notat cu {$P$}) din setul {$I$}. In cazul in care punctul {$P$} se afla in interiorul cercului {$C{~I-{P},B~}$}, atunci cercul acesta nu mai trebuie marit si {$C{~I,B~}$} devine egal cu {$C{~I-{P},B~}$}. In cazul in care punctul {$P$} nu se afla in interiorul acelui cerc {$C{~I,B~}$} devine egal cu {$C{~I-{P},B U {P}~}$}.

Singura neclaritate care ramane este _de ce_ complexitatea este {$O(N)$}. Datorita alegerii punctelor in mod random in timpul calcularii lui {$C{~I,B~}$}, fiecare punct din {$I$} are probabilitatea {$^1^/{~|I|~}$} de a fi ales. Pe masura ce calculam {$C{~I,B~}$}, pastrand acelasi {$B$}, pot exista doar 3 puncte {$P$} pentru care este nevoie sa calculam {$C{~I,B+{P}~}$}.

Singura neclaritate care ramane este _de ce_ complexitatea este {$O(N)$}. Datorita alegerii punctelor in mod random in timpul calcularii lui {$C{~I,B~}$}, fiecare punct din {$I$} are probabilitatea {$^1^/{~|I|~}$} de a fi ales. Pe masura ce calculam {$C{~I,B~}$}, pastrand acelasi {$B$}, pot exista doar 3 puncte {$P$} pentru care este nevoie sa calculam {$C{~I,B U {P}~}$}.

TODO explicatie complexitate scrisa ceva mai bine, poza