!algoritmi-de-baleiere?fig1.jpg!

In timpul baleierii, la fiecare pas trebuie sa avem la dispozitie o structura de date continand toate obiectele intersectate de linia de baleiere. Pentru exemplul de mai sus, multimea de obiecte e traversata de sus in jos, iar la pasul curent sunt intersectate obiectele $b$, $d$, $e$, $f$. Continuand traversarea, vor urma, in ordine, eliminarea lui $b$ din structura de date, eliminarea lui $d$, adaugarea lui $g$, etc. Dupa cum se observa, multimea obiectelor intersectate sufera destule modificari, ceea ce ne determina sa alegem o structura de date dinamica care sa ne confere eficienta. De cele mai multe ori, alegerea noastra va fi un arbore echilibrat.

In timpul baleierii, la fiecare pas trebuie sa avem la dispozitie o structura de date continand toate obiectele intersectate de linia de baleiere. Pentru exemplul de mai sus, multimea de obiecte e traversata de sus in jos, iar la pasul curent sunt intersectate obiectele $b$, $d$, $e$, $f$. Continuand traversarea, vor urma, in ordine, eliminarea lui $b$ din structura de date, eliminarea lui $d$, adaugarea lui $g$, etc. Dupa cum se observa, multimea obiectelor intersectate sufera destule modificari, ceea ce ne determina sa alegem o structura dinamica de date care sa ne confere eficienta. De cele mai multe ori, alegerea noastra va fi un arbore echilibrat. In cadrul algoritmului, vom vrea sa stim si care sunt momentele la care multimea obiectelor intersectate sufera modificari. Aceste momente vor reprezenta _evenimentele_, iar multimea acestora se va numi _lista de evenimente_. Iata pasii unui algoritm de baleiere (pastram notatia $Q$ pentru intrebarea pe care o adresam):
 
== code(c) |
Initializeaza lista de evenimente (L)
Initializeaza multimea obiectelor intersectate (M)
CAT TIMP L este nevida
    Sterge evenimentul care urmeaza din L
    DACA un nou obiect este intersectat de linia de baleiere
        Adauga-l in M
    DACA un obiect inceteaza a mai fi intersectat
        Sterge-l din M
    Aduna informatii privitoare la intrebarea Q
    DACA este cazul
        Adauga noi evenimente in L
==

h2(#baleiere_verticala). Baleiere verticala