* 'Introducere':algoritmi-de-baleiere#introducere
* 'Prezentarea metodei':algoritmi-de-baleiere#prezentare
* 'Baleiere verticala':algoritmi-de-baleiere#baleiere_verticala

* 'Baleiere rotationala':algoritmi-de-baleiere#baleiere_rotationala

* 'Baleiere radiala':algoritmi-de-baleiere#baleiere_radiala

* 'Un alt algoritm pentru infasuratoarea convexa':algoritmi-de-baleiere#infasuratoare_convexa
* 'Aplicatii':algoritmi-de-baleiere#aplicatii
* 'Bibliografie':algoritmi-de-baleiere#bibliografie

Sa vedem acum analiza complexitatii. Avem nevoie de un timp $O(N * log N)$ pentru sortarea listei de evenimente dupa abscisa, $O(log N)$ (sau chiar $O(1)$ la heap-uri si la $set$-urile din STL) pentru alegerea obiectului cu ordonata maxima, $O(log N)$ pentru inserare si stergere in structura de date aleasa. Intrucat sunt $2 * N$ evenimente (cate 2 capete pentru fiecare segment), iar pentru fiecare efectuam o interogare si o adaugare / stergere, complexitatea finala va fi $O(N * log N) + O(N) * (O(log N) + O(log N)) = O(N * log N)$.

Problema de fata poate fi generalizata pentru cazul in care dreptunghiurile nu au o latura fixata, ci sunt oarecare in plan. Pentru acest lucru, la fiecare eveniment va fi necesara o parcurgere integrala a multimii de obiecte intersectate de linia de baleiere, ceea ce conduce la un timp de executie patratic $O(N^2^)$. Lasam aceasta aplicatie ca un exercitiu pentru cititor.

Situatia se poate complica daca dreptunghiurile nu au o latura fixata pe axa $OX$. Nu mai este suficienta o simpla extragere a elementului maxim din structura de date, ci trebuie sa retinem mult mai multe informatii pentru a pastra complexitatea $O(N * log N)$. Aceasta generalizare a fost data la Olimpiada Baltica de Informatica din 2001 (problema Mars Maps).

h2(#baleiere_rotationala). Baleiere rotationala

h2(#baleiere_radiala). Baleiere radiala

h2(#infasuratoare_convexa). Un alt algoritm pentru infasuratoarea convexa

Baleierea verticala nu este singura modalitate de scanare a planului. Pentru exemplificarea acestui lucru, se poate porni tot de la o situatie concreta: avand $N$ puncte in plan, vrem sa aflam numarul maxim de puncte coliniare. O solutie triviala ar fi sa se fixeze 2 puncte si sa se numere toate punctele coliniare cu cele 2 dintre cele ramase. Complexitatea totala ar fi $O(N^3^)$ care, in mod evident, nu este multumitoare. O imbunatatire semnificativa a algoritmului se obtine folosind tehnica de baleiere: se fixeaza un punct si se scaneaza planul cu ajutorul unei semidrepte avand originea in punctul fixat. Rotind semidreapta si suprapunand-o peste un punct, numaram daca mai exista si altele peste care s-a suprapus. Nu trebuie sa ne ingrijoreze faptul ca pot fi puncte coliniare cu unele gasite deja, dar care se afla in sensul opus celui dat de semidreapta aleasa, pentru ca oricum vom face o baleiere in fiecare punct si intr-unul din ele le vom numara corect in mod sigur pe cele coliniare. Implementarea eficienta a acestei metode presupune ca, odata fixata originea semidreptei, sa se sorteze toate celelalte puncte in functie de unghiul polar relativ la punctul fix. Complexitatea ajunge, astfel, la $O(N^2^ * log N)$.
 
O aplicatie ceva mai spectaculoasa a baleierii radiale este gasirea unui triunghi dreptunghic cu varfurile printre $N$ puncte date. Fixand un punct, putem cauta un triunghi dreptunghic care sa aiba unghiul drept in acel punct. Pentru acest lucru, vom sorta punctele exact ca la problema precedenta, dar baleierea o vom face rotind simultan 2 semidrepte cu originile in punctul fix, intre care mentinem in orice moment un unghi de 90 de grade. Cand ambele semidrepte se vor suprapune peste cate un punct, vom gasi ceea ce cautam. Complexitatea acestui algoritm va fi tot $O(N^2^ * log N)$.

*Cosmin:* Articolul asta despre baleiere http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep e destul de bine facut, poti sa trimiti lumea sa il citeasca. De asemenea in articolul lui Mircea despre arbori de intervale prezinta cate ceva despre linii de baleiere.

h2(#infasuratoare_convexa). Un alt algoritm pentru infasuratoarea convexa

h2(#aplicatii). Aplicatii

Iata si o scurta lista de probleme care merita implementate:
 
* BOI 2001: 'Mars Maps':http://www.ii.uni.wroc.pl/boi/index.phtml?id=11
 

h2(#bibliografie). Bibliografie

 
 
 
*Cosmin:* Articolul asta despre baleiere http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep e destul de bine facut, poti sa trimiti lumea sa il citeasca. Chestia cu aria dreptunghiurilor nu e explicata si in articolul lui Mircea despre arbori de intervale? Mai bine ii trimiti acolo direct, decat sa le mai prezinti acelasi lucru inca o data. Si acolo parca complexitatea e O(n log n) in total.
 
*Stefan:* Articolul de pe Topcoder o sa-l mentionez impreuna cu altele la bibliografie. La complexitatea problemei cu aria dreptunghiurilor ai avut dreptate si este $O(N * log N)$ (am modificat asta in articol). Cat despre articolul cu 'arbori de intervale':arbori-de-intervale (singurul astfel de articol in romana de care stiu este al doamnei Dana Lica, nu al lui Mircea), acolo este prezentata in detaliu aplicatia cu perimetrul reuniunii de dreptunghiuri, iar cea cu aria este trecuta doar la Probleme propuse. In plus, aplicatia pe care o prezint eu nu vrea sa reproduca pe niciuna din ele, ci este o varianta mult mai simplificata pentru a prezenta tehnica de baleiere. In problema pe care o prezint, un query sau un update vizeaza un singur element dintr-o multime, pe cand in problema generala a ariei dreptunghiurilor, update-ul vizeaza un interval de elemente.
 
*Cosmin:* :) da e al doamnei Lica .... perimetrul nu merge in O(n log n) perimetru e O(n log n + nr de segmente de pe perimetru) nu am citit articolul dar tind sa cred ca e prezentata treaba cu aria.