5 0 5 8
7 5 7 11  |^. 4 |=. !arbori-de-intervale?figure-1.jpg! |

h2. Algoritmi de "baleiere" _(line sweeping)_

h2. Rezolvare

p<>. Folosind cunostinte generale de geometrie analitica se poate obtine un algoritm $O(N^2^)$ dar acesta nu se va incadra in limita de timp.

 
h2. Algoritmi de "baleiere" _(line sweeping)_
 

p<>. Pentru rezolvarea acestei probleme vom folosi o tehnica cunoscuta sub numele de "baleiere" _(sweeping)_ care este comuna multor algoritmi de geometrie computationala. In baleiere, o dreapta de baleiere verticala, imaginara, traverseaza multimea obiectelor geometrice, de obicei de la stanga la dreapta.  Baleierea ofera o metoda pentru ordonarea obiectelor geometrice, plasandu-le intr-o structura de date, pentru obtinerea relatiilor dintre ele.
Algoritmii de baleiere gestioneaza doua multimi de date: