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 {$C{~i~}$} cercul de raza minima ce include primele i puncte.
Notam cu {$C{~I~}$} cercul de raza minima ce contine in interior punctele din setul {$I$}.
Pentru fiecare punct {$P{~i+1~}$}, putem determina in timp constant daca punctul se afla in interiorului cercului {$C{~i~}$}. In cazul in care {$P{~i+1~}$} este inclus in {$C{~i~}$}, atunci {$C{~i+1~}$} 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{~N~}$}, unde {$N$} este numarul de puncte din set. 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+{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.
!>minimum-enclosing-circle?punctlasatinext.png 63%! La o prima vedere se pare ca trebuie doar sa calculam cel mai mic cerc ce include {$P{~i+1~}$} alaturi de cele 3 puncte ce determinau {$C{~i~}$} fara sa mai luam in considerare celelalte puncte din set, insa nu este greu de gasit un caz pentru care raman puncte in exterior, asa cum se vede in poza alaturata.
!>minimum-enclosing-circle?punctlasatinext.png 63%! La o prima vedere se pare ca trebuie doar sa calculam cel mai mic cerc ce include {$P$} alaturi de cele 3 puncte ce determinau {$C{~I~}$} fara sa mai luam in considerare celelalte puncte din set, insa nu este greu de gasit un caz pentru care raman puncte in exterior, asa cum se vede in poza alaturata.
Vom demonstra in continuare ca daca punctul {$P{~i+1~}$} se afla in exteriorul cercului {$C{~i~}$}, atunci el trebuie sa fie pe circumferinta cercului {$C{~i+1~}$}.
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}~}$}.
* {!>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 {$π$} (cel albastru in poza alaturata). Daca arcul de cerc ar avea o lungime mai mare ca {$π$} 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{~i+1~}$} nu apartine circumferintei cercului {$C{~i+1~}$}. Este usor de vazut ca raza cercului {$C{~i~}$} este mai mica ca cea a cercului {$C{~i+1~}$}, deoarece {$C{~i+1~}$} 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+1~}$}, atunci intersectia cercului {$C{~i+1~}$} cu interiorul cercului {$C{~i~}$} este un arc de cerc de lungime mai mica ca {$π$}.
* Datorita faptului ca {$P{~i+1~}$} nu apartine circumferintei cercului {$C{~i+1~}$}, punctele care definesc cercul {$C{~i+1~}$} se afla printre punctele {{$P{~1~}$}, {$P{~2~}$}, ..., {$P{~i~}$}}. Cum toate aceste puncte se afla in interiorul cercului {$C{~i~}$} si intersectia cercului {$C{~i+1~}$} cu interiorul cercului {$C{~i~}$} este un arc de cerc de lungime mai mica decat {$π$}, punctele care determina cercul {$C{~i+1~}$} trebuie sa se afle pe acest arc de cerc. Astfel avem cel putin 2 puncte consecutive pe circumferinta cercului {$C{~i+1~}$} 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{~i+1~}$} trebuie sa se afle pe circumferinta cercului {$C{~i+1~}$}.
* 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}~}$}.
Acum trebuie doar sa calculam cel mai mic cerc care contine punctele {{$P{~1~}$}, {$P{~2~}$}, ..., {$P{~i~}$}} in interior si care are {$P{~i+1~}$} pe circumferinta. Notam cu {$D2{~I,C~}$} cercul de raza minima ce contine punctele din setul I in interior si punctele din setul C pe circumferinta in mod obligatoriu. Pentru a determina {$D2{~i,C~}$} vom proceda in mod asemanator ca pana acum. {$D{~i~}$} poate fi scris ca D2{~i,{}~}.
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}~}$}.
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 {$D{~I,B+{P}}$}.
Exercitii: "SPOJ ALIENS":http://www.spoj.pl/problems/ALIENS/
