Diferente pentru minimal-enclosing-circle intre reviziile #6 si #51

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Minimal enclosing circle
(Categoria _Geometrie_, 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_.
h2. 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.
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. Daca pe cerc exista 2 puncte consecutive ce formeaza un arc de cerc mai mare de {$π$}, atunci cercul poate fi micsorat, ducand centrul cercului inspre segmentul format de cele 2 puncte. Astfel, 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:
Algoritmul descris are complexitate {$O(N^3^)$} pentru generarea cercurilor si inca {$O(N)$} pentru fiecare cerc pentru verificare, in total avand {$O(N^4^)$}.
h2. Algoritm {$O(N^2^)$}
h2. Algoritm {$O(N^2^)$} !>minimal-enclosing-circle?schema.gif!
 
Algoritmul acesta se bazeaza pe aceleasi observatii ca mai sus. Se porneste de la un cerc mare care sigur cuprinde toate punctele si se micsoreaza la fiecare pas raza cercului cat mai mult posibil.
 
# 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. )
# 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.
... TODO de scris... am gif dragutz animat :P
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.
 
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.
 
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}~}$}.
 
* {!>minimal-enclosing-circle?figura.png 40%!} 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 &#8746; {P}~}$}. Este usor de vazut ca raza cercului {$C{~I~}$} este mai mica ca cea a cercului {$C{~I &#8746; {P}~}$}, deoarece {$C{~I &#8746; {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 &#8746; {P}~}$}, atunci intersectia cercului {$C{~I &#8746; {P}~}$} cu interiorul cercului {$C{~I~}$} este un arc de cerc de lungime mai mica ca {$&pi;$}.
* Datorita faptului ca {$P$} nu apartine circumferintei cercului {$C{~I &#8746; {P}~}$}, punctele care definesc cercul {$C{~I &#8746; {P}~}$} se afla printre punctele din setul {$I$}. Cum toate aceste puncte se afla in interiorul cercului {$C{~I~}$} si intersectia cercului {$C{~I &#8746; {P}~}$} cu interiorul cercului {$C{~I~}$} este un arc de cerc de lungime mai mica decat {$&pi;$}, punctele care determina cercul {$C{~I &#8746; {P}~}$} trebuie sa se afle pe acest arc de cerc. Astfel avem cel putin 2 puncte consecutive pe circumferinta cercului {$C{~I &#8746; {P}~}$} care formeaza un arc de cerc de lungime mai mare {$&pi;$} (cel rosu in poza alaturata).
* Acest lucru intra in contradictie cu faptul ca cercul are raza minima. Astfel {$P$} trebuie sa se afle pe circumferinta cercului {$C{~I &#8746; {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,&#216;~}$}.
 
Calcularea lui {$C{~I,B~}$} se va face in mod recursiv. Mai jos voi prezenta un pseudocod pentru functia respectiva:
 
==code(c) |
Cerc MINCIRCLE( Set I, Set B )
    Daca |I| == 0 sau |B| >= 3
        returneaza cercul format de punctele din B
    P = punct random apartinand setului I
    C = MINCIRCLE( I - {P}, B )
    Daca P nu este inclus in C
        returneaza MINCIRCLE( I - {P}, B + {P} )
    returneaza C
==
 
Singurul lucru care mai ramane de demonstrat este _de ce_ complexitatea este {$O(N)$}.
 
Pentru {$|B|$} egal cu 3, cercul este foarte usor de determinat in complexitate {$O(1)$}.
 
Pentru {$|B|$} egal cu 2, complexitatea este evident {$O(N)$}, deoarece calcularea cercului de raza minima pentru setul {$B + {P}$} se rezolva in {$O(1)$}.
 
Pentru {$|B|$} egal cu 1, notam cu {$T(N)$} numarul mediu de operatii folosite pentru a calcula {$C{~S,B~}$}, unde {$|S|$} este egal cu {$N$}.
 
Din setul {$I$} vom scoate un element la fiecare apelare a functiei MINCIRCLE, deci pentru a calcula numarul mediu de operatii pentru {$N$} elemente, adunam numarul mediu de operatii pentru {$N - 1$} elemente ({$T(N - 1)$}).
Fiecare punct din {$I$} are probabilitatea {$^1^/{~N~}$} de a fi ales in cadrul functiei. Din aceasta cauza, functia MINCIRCLE{$(I - {P}, B &#8746; {P})$} va fi apelata cu o probabilitate egala cu (numarul de puncte {$P$} care nu apartin cercului {$C{~I - {P},B~}$}) / {$N$}. De asemenea, fiecare apel al acestei functii are complexitatea {$O(N)$}, dupa cum am demonstrat mai sus pentru {$|B|$} egal cu 2.
 
Astfel {$T(N)$} respecta relatia:
 
* {$T(N) <= T(N - 1) + Probabilitatea( P &notin; C{~I - {P},B~} ) * O(N) + O(1)$}
 
Datorita faptului ca cercul de raza minima care cuprinde toate punctele din setul {$I$} este determinat de 2 sau 3 puncte, la fiecare apel al functiei exista maxim 3 puncte pentru care cercul {$C{~I - {P},B~}$} va trebui marit. Astfel probabilitatea ca {$P$} sa nu apartina cercului {$C{~I - {P},B~}$} este egala cu {$^3^/{~N~}$}. Inegalitatea devine:
 
* {$T(N) <= T(N - 1) + ^3^/{~N~}*O(N) + O(1)$}
ceea ce este echivalent cu
* {$T(N) <= T(N - 1) + O(1)$}
h2. Istoria problemei
Astfel complexitatea devine {$O(N)$}. Demonstratia pentru {$|B|$} egal cu 0 se face in mod asemanator.
... TODO.. non-important.. may be removed in final form :P
Ca o ultima precizare, exista si un algoritm de complexitate {$O(N log N)$} pentru aceasta problema, ce foloseste diagrame voronoi.
Exercitii: "SPOJ ALIENS":http://www.spoj.pl/problems/ALIENS/

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3684