Se da urmatoarea problema:
Se dau n cercuri in planul xOy determinate de coordonatele centrului si raza r.
Sa se gaseasca numarul minim de drepte verticale care sa le intersecteze pe toate.

Ce abordare sugerati pentru aceasta problema? (Algoritm)

M-am gandit ca pentru aceste cercuri, in contextul problemei este relevant diametrul, paralel cu axa ox, adica segmentul determinat de punctele: cel mai din stanga si cel mai din dreapta a cercului.

Asadar, problema s-ar transforma in a gasi nr. minim de drepte verticale care intersecteaza n segmente a caror capete se cunosc.

Care ar fi o un algoritm eficient de rezolvare a acestei probleme? M-am gandit sa ma folosesc de o sortare a segmentelor, de exemplu dupa capatul din stanga, urmat de o parcurgere.

De asemenea, am citit despre Line Sweep Algorithm, dar nu sunt foarte in tema deocamdata. Ar putea fi folosit?

Multumesc.

[Citat] Se da urmatoarea problema: Se dau n cercuri in planul xOy determinate de coordonatele centrului si raza r. Sa se gaseasca numarul minim de drepte verticale care sa le intersecteze pe toate. Ce abordare sugerati pentru aceasta problema? (Algoritm) M-am gandit ca pentru aceste cercuri, in contextul problemei este relevant diametrul, paralel cu axa ox, adica segmentul determinat de punctele: cel mai din stanga si cel mai din dreapta a cercului. Asadar, problema s-ar transforma in a gasi nr. minim de drepte verticale care intersecteaza n segmente a caror capete se cunosc. Care ar fi o un algoritm eficient de rezolvare a acestei probleme? M-am gandit sa ma folosesc de o sortare a segmentelor, de exemplu dupa capatul din stanga, urmat de o parcurgere. De asemenea, am citit despre Line Sweep Algorithm, dar nu sunt foarte in tema deocamdata. Ar putea fi folosit? Multumesc.

In orice caz, problema depinde numai de proiectiile cercurilor pe axa Ox.
Este insa neclar ce este acel numar *minim* de drepte verticale.
In ce sens minim?

(Acesta este enuntul exact?!)

Da, acesta este enuntul.

Adica numarul minim de drepte verticale care trebuie sa fie trasate, astfel incat sa nu ramana niciun cerc netaiat de macar o dreapta.

Spre exemplu, daca am avea ca proiectii ale cercurilor intervalele urmatoare: [1,4] [3,5] [9,10] acest numar minim de drepte ar fi 2.

Dupa alte cercetari, cred ca un arbore de intervale (https://en.wikipedia.org/wiki/Interval_tree) ar fi bine venit in rezolvarea problemei, alaturi de o functie de overlapping(suprapunere) a intervalelor.

Atunci problema este urmatoarea:

[Citat] Se dau n cercuri in planul xOy determinate de coordonatele centrului si (de una si aceeasi?!) raza r. O multime de drepte verticale este "buna" daca fiecare cerc este intersectat (in doua puncte?!) de cel putin una din dreptele din multime. Sa se gaseasca numarul minim N de drepte dintr-o multime buna. (In sensul ca N se atinge pentru o anumita multime buna, care trebuie gasita algoritmic explicit, si pentru orice alta multime buna de drepte numarul lor este mai mare sau egal cu N.)

In primul rând trebuie clarificat daca toate cercurile au una si aceeasi (marime de) raza r. Este asa?

Daca da, ceea ce reiese din enunt, atunci putem presupune fara a restrânge generalitatea ca r = 1 .

Apoi ne legam de intervalele de lungime 2 obtinute prin proiectia cercurilor pe axa Ox. Ordonam aceste intervale dupa extremitatea lor stânga, eliminam fara probleme suprapunerile de intervale, si obtinem intervale:

I1 = [a1,b1], I2 = [a2,b2], I3 = [a3,b3], ...

Acum un algoritm se descrie destul de simplu.
Este clar ca trebuie sa "taiem " I1, de aceea il taiem "optimal" cu o verticala prin b1-epsilon1, mai vedem noi ce e epsilon1 curând...

Vedem câte intervale am taiat deja si le taiem de pe lista.
Procedam la fel cu primul interval ramas...

Cred ca e usor acum de vazut cât de mici trebuie luate "epsilonurile" care mai intervin pe drum...

[Citat] Dupa alte cercetari, cred ca un arbore de intervale (https://en.wikipedia.org/wiki/Interval_tree) ar fi bine venit in rezolvarea problemei, alaturi de o functie de overlapping(suprapunere) a intervalelor.

Aceasta este probabil ideea valabilă. Practic, proiecția discurilor pe axa orizontală generează niște intervale disjuncte. Dacă etichetăm discurile cu 1, 2, ..., n, atunci asociem fiecărui interval mulțimea discurilor a căror proiecție pe interval este nevidă. În final, eliminăm toate intervalele "nemaximale". Exemplu: intervalul I_1 are asociată mulțimea {1, 2, 5, 7}, iar intervalul I_2 are asociată mulțimea {2,7}. Atunci intervalul I_2 poate fi eliminat, deoarece orice intervalul I_1 este "mai bun" din toate punctele de vedere (orice dreaptă verticală prin I_1 trece prin discurile 1, 2, 5 și 7).

Evident, implementarea este altă poveste.