Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-02-01 12:18:57.
Revizia anterioară   Revizia următoare  

Minimal enclosing circle

(Categoria Geometrie analitica, 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.

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. 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:

  • 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)

Algoritmul acesta se bazeaza pe aceeasi 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.

  1. Se construieste un cerc de raza suficient de mare incat sa cuprinda toate punctele in mod sigur (raza infinit) si un centru ales aleator.
  2. 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.
  3. 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. )
  4. 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:
    1. centrul cercului ajunge pe segmentul DE. In acest moment DE a devenit diametru in cerc si am determinat cercul de raza minima
    2. 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(N2).

Algoritm O(N)

Algoritmul acesta construieste cercul in mod incremental, adaugand pe rand puncte in cercul de raza minima.

Notam cu CI 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 CI. In cazul in care P este inclus in CI, atunci CI ∪ {P} va fi egal cu CI. In caz contrar, trebuie sa schimbam cercul CI pentru a cuprinde si acest punct. Cercul ce cuprinde toate punctele va fi evident CS, 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 CI, atunci el trebuie sa fie pe circumferinta cercului CI ∪ {P}.

  • Dandu-se doua cercuri de raza R1 si R2, avand R1 < R2, atunci intersectia cercului de raza R2 cu interiorul cercului de raza R1 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 2R2, insa in cercul de raza R1 cea mai mare distanta intre 2 puncte din interiorul sau poate fi maxim 2R1. Cum R1 < R2, acest lucru este imposibil.
  • Presupunem prin reducere la absurd ca P nu apartine circumferintei cercului CI ∪ {P}. Este usor de vazut ca raza cercului CI este mai mica ca cea a cercului CI ∪ {P}, deoarece CI ∪ {P} cuprinde un punct care nu este cuprins de CI. Daca notam cu R1 raza cercului CI si cu R2 raza cercului CI ∪ {P}, atunci intersectia cercului CI ∪ {P} cu interiorul cercului CI este un arc de cerc de lungime mai mica ca π.
  • Datorita faptului ca P nu apartine circumferintei cercului CI ∪ {P}, punctele care definesc cercul CI ∪ {P} se afla printre punctele din setul I. Cum toate aceste puncte se afla in interiorul cercului CI si intersectia cercului CI ∪ {P} cu interiorul cercului CI este un arc de cerc de lungime mai mica decat π, punctele care determina cercul CI ∪ {P} trebuie sa se afle pe acest arc de cerc. Astfel avem cel putin 2 puncte consecutive pe circumferinta cercului CI ∪ {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 CI ∪ {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 CI adaugand un nou parametru. Astfel notam cu CI,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 CS,{}.

Calcularea lui CI,B se face in mod recursiv. Daca B are cel putin 3 puncte atunci CI,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 CI-{P},B, atunci cercul acesta nu mai trebuie marit si CI,B devine egal cu CI-{P},B. In cazul in care punctul P nu se afla in interiorul acelui cerc CI,B devine egal cu CI-{P},B ∪ {P}.

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

TODO explicatie complexitate scrisa ceva mai bine, poza

Exercitii: SPOJ ALIENS