h3. Rezolvare:

Mai întâi facem vom face două observaţii:

Mai întâi vom face două observaţii:

În configuraţia cu număr maxim de regiuni nu vom avea două drepte paralele, pentru că două drepte care se intersectează formează în plan patru regiuni, în timp ce două drepte paralele formează în plan doar trei regiuni.
De asemenea pentru a obţine un număr maxim de regiuni, nu vor exista trei drepte care să se intersecteze intr-un punct pentru că astfel am pierde o regiune triunghiulară formată din punctele de intersecţie ale celor trei drepte.

Dacă aceste două condiţii sunt îndeplinite vom vedea în continuare că orice configuraţie de $N$ drepte împarte planul în acelaţi număr de regiuni. Notăm cu $d(n)$ acest număr. Presupunem ca ştim pe $d(n)$ , să vedem acum ce se întâmplă dacă mai adaugăm o dreaptă.

Dacă aceste două condiţii sunt îndeplinite vom vedea în continuare că orice configuraţie de $N$ drepte împarte planul în acelaşi număr de regiuni. Notăm cu $d(n)$ acest număr. Presupunem ca ştim pe $d(n)$ , să vedem acum ce se întâmplă dacă mai adaugăm o dreaptă.

Această nouă dreaptă va fi intersectată de celelalte drepte în $n$ puncte distincte. Fiecare segment de dreaptă şi semidreaptă în care este împărţită a $n+1-a$ taie o regiune veche in două regiuni noi. De aici tragem concluzia că $d(n+1) = d(n) + n + 1$ . Deci $d(n) = n + n – 1 + n – 2 + … + 2 + d(1)$ . Astfel folosind indentitatea $1 + 2 + 3 + … + n = n(n+1)/2$ obţinem $d(n) = n(n + 1) / 2 + 1$ .
Menţionăm că problemele în care se cere maximizarea numărului de regiuni în care un pătrat, un triunghi sau un cerc este împărţit de $n$ drepte, au aceiaşi soluţie.

h3. Rezolvare:

Contraexemple rezolvare normala

O rezolvare folosind geometria computaţională pare foarte grea, lucrurile simplificându-se mult daca abordam problema prin prisma unor noţiuni de teoria grafurilor.
Fiecare punct de intersectie va fi considerat un nod. Două noduri vor fi legate prin o muchie dacă există un cerc pe care sa se afle amândouă iar între ele să nu existe nici un alt punct de intersectie.
Acum vom folosi identitatea lui Euler: prezentată în problema anterioară. În problema noastră nu trebuie să numărăm şi faţa exterioară, deci formula folosita va fi $F=M-V+1$ . Această formulă este adevarată doar in cazul unei singure componente conexe. Pentru mai multe componente, formula devine $F=M-V+C$ , unde $C$ este numărul de componente conexe.
O atenţie deosebită trebuie acordată punctelor de intersecţie prin care trec mai mult de două cercuri, pentru a nu le număra de mai multe ori. Putem rezolva aceasta problema prin sortarea punctelor de intersecţie ale unui cerc cu toate celelalte cercuri.
Deasemenea, este necesara eliminarea cercurilor identice (cu acelaşi centru şi raze egale). Din orice mulţime cu astfel de cercuri este păstrat doar un singur element.

Deoarece pentru fiecare cerc este necesara o sortare a punctelor de intersectie, complexitatea generala a algoritmului va fi $O(N2*log(N))$

Deoarece pentru fiecare cerc este necesara o sortare a punctelor de intersectie, complexitatea generala a algoritmului va fi $O(N^2^*log(N))$

h2(#bibliografie). Bibliografie: