== include(page="template/implica-te/scrie-articole" user_id="alecman") ==

(Categoria _Structuri de date_, autor _Cosmin Negruseri_)

(Categoria _Structuri de date_, Autor _Cosmin Negruseri_)

h2. Introducere

In +problema 3+ a zilei 2 a **Balcaniadei de Informatica** din 1997, se da un _QuadTree_ care reprezinta o imagine colorata alb-negru, de dimensiune $2^N^ * 2^N^$. Daca patratul reprezentat de informatia dintr-un nod al arborelui era de aceeasi culoare, in nod se pastra informatia culorii si nodul nu avea nici un fiu, altfel nodul avea starea indecisa/nedeterminata si avea patru fii.

!cautari-ortogonale?pic1.jpg!

p=. !cautari-ortogonale?pic1.jpg!

!cautari-ortogonale?pic2.jpg!
!cautari-ortogonale?pic5.jpg!

_kD-Tree_ este o structura de date care organizeaza o multime de puncte in $k$ dimensiuni, imparte spatiul in semispatii astfel ca fiecare nod din arbore reprezinta un paralelipiped si contine in el un punct. Noi suntem interesati de arbori 2D in special. Pentru cazul 2D, primului nod ii va fi asociat intreg planul. Se duce o linie verticala de abscisa $x$ care imparte planul in doua si punctele in doua multimi de cardinal egal. Subarborele din stanga va contine toate punctele din stanga acestei drepte verticale, iar subarborele din dreapta va contine toate punctele din dreapta acestei drepte verticale. Radacinei arborelui din stanga ii va fi asociat semiplanul stang determinat de dreapta verticala, si va contine punctul median dintre punctele din semiplanul stang sortate dupa $y$. Astfel, la nivel impar punctele vor fi mediane din sirul punctelor sortat dupa $x$, iar la nivel par punctele vor fi mediane din sirul punctelor sortat dupa $y$. Pentru mai multe dimensiuni ale spatiului ciclam dupa $d{~1~}$, $d{~2~}$,..., $d{~n~}$ si apoi iar $d{~1~}$ ca sa punem elementul median pe nivelul curent. In cazul 2D complexitatea crearii unui asemenea arbore e $O(n log n)$. Pentru a raspunde la query-uri pe un dreptunghi coboram in arbore in fii pentru care domeniul asociat se intersecteaza cu dreptunghiul nostru. Se poate demonstra ca aceasta operatie are timpul de executie in cel mai rau caz $O(sqrt(n))$.

p=. !cautari-ortogonale?pic7.jpg!
 

Unele implementari tin puncte numai in frunze, si in nodurile care nu sunt frunze tin numai informatia despre coordonata dreptei care imparte regiunea in doua. Dimensiunile regiunii asociate unui nod pot fi tinute in nod sau pot fi calculate la fiecare operatie pentru a salva spatiu. O alta idee pentru a mari viteza de cautare in arbori kD ar fi sa nu alegem ciclic pe ce directie impartim punctele, ci sa alegem la fiecare pas directia pe care punctele sunt cele mai imprastiate.
Pseudocod pentru constructie:

Timp de executie: $0.5 secunde$

!cautari-ortogonale?pic6.jpg!

p=. !cautari-ortogonale?pic6.jpg!

Rezolvam aceasta problema folosind paradigma liniei de baleiere. Sortam dreptunghiurile dupa coordonata $x$ a coltului din dreapta. Dupa cum observam in figura alaturata exista trei pozitii relative ale doua dreptunghiuri care se intersecteaza. Cazurile 1, 2, 4, 5 si 6 se reduc la intersectia laturii verticale din stanga a unui dreptunghi cu latura orizontala de sus a celuilalt dreptunghi, deci acest gen de intersectii pot fi numarate numarand intersectiile intre segmentele orizontale si verticale (aceasta problema a fost deja tratata in articolul [1]). Mai raman cazurile 3 si 7 in care coltul din stanga sus al celui de al doilea dreptunghi e in interiorul primului, acest tip de query il rezolvam cu ajutorul arborilor de intervale, intai inseram in structura toate punctele din dreapta sus ale dreptunghiurilor si apoi pentru fiecare dreptunghi facem query pentru a afla numarul de puncte din interiorul lui.

h2. Bibliografie
# 'Arbori de intervale ("segment trees") si aplicatii in Geometria Computationala, Dana Lica':arbori-de-intervale

# 'Arbori Indexati Binar, Mihai Scortaru, GInfo':http://www.ginfo.ro/revista/13_1/focus.pdf

# 'Arbori Indexati Binar, Mihai Scortaru, GInfo':http://www.ginfo.ro/revista/13_1/focus.pdf
# 'Kd-Trees, Andrew W. Moore':http://www.autonlab.org/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en

3692