altfel returneaza cauta(nod-kD.stanga, Q) reunita cu cauta(nod-kD.dreapta, Q)
==
Sa vedem care e complexitatea operatiei **cauta**. Nodurile care sunt total in afara dreptunghiului sau total inauntrul dreptunghiului Q pot cel mult fi de doua ori mai multe decat nodurile care intersecteaza dreptunghiul Q intr-o cautare, pentru ca vizitarea unui nod total in afara dreptunghiului sau unui nod dinauntrul dreptunghiului a pornit de la un nod al carui domeniu intersecteaza dreptunghiul. Pentru analiza ne putem ocupa numai de noduri ale caror domenii intersecteaza dreptunghiul. Pentru a obtine o limita superioara a numarului de zone intersectate putem considera numarul maxim de zone intersectate de o latura a dreptunghiului si sa inmultim acel numar cu patru. Pentru a mai simplifica analiza putem considera nu numarul maxim de zone intersectate de un segment, ci numarul maxim de zone intersectate de o dreapta verticala sau orizontala. Consideram o dreapta verticala, pentru un nod, daca directia de impartire a zonei asociate e verticala atunci dreapta verticala taie sau zona fiului stang sau zona fiului drept, dar nu pe amandoua deodata. Daca dreapta verticala nu intersecteaza zona asociata unui fiu atunci nu va mai intersecta zona nici unui urmas al fiului. In caz contrar intersecteaza ambii fii. Daca coboram la nivelul nepotilor cel mult patru noduri sunt intersectate. In cel mai rau caz intersectam domeniul reprezentat de radacina si putem intersecta cel mult $2^i^$ noduri pana la nivelul $2i$. Deci in total maxim O(sqrt(n)) noduri sunt parcurse la o operatie cauta.
Avantajul arborilor kD ar fi usurinta in implementare si spatiul de memorie O(n) folosit, dezavantajul ar fi timpul O(sqrt(n)) pentru cautare, dar avand in vedere ca arborii de intervale sau arborii indexati binar au complexitatea O(log^2^ n) la cautare, timpii sunt comparabili.
Arborii de intervale au fost prezentati in articolul [1] deci nu mai insist asupra lor.
Arborii indexati binar sunt si ei folositori si au fost prezentati [2]. Dezavantajul arborilor indexati binar este ca ei pot fi folositi la numarare si la sume, dar nu la aflarea minimului sau maximului pe un interval. Singura posibilitate cand maximul sau minimul pot fi aflate este atunci cand intervalele pe care facem cautarea sunt nemarginite in sus sau in jos. In schimb la toate structurile despre care am discutat pana acuma putem raspunde in timp subliniar la intrebari despre maxim si minim. Alt dezavantaj este ca daca trebuie sa pastram in spatiul cu $n$ dimensiuni de la $0$ pana la $N$ atunci trebuie sa folosim $N^n^$ spatiu, insa acest neajuns il putem evita folosind impreuna cu arborele indexat binar si o tabela de dispersie. Facand aceasta folosim numai O(nr log^2^ N) spatiu pentru $nr$ puncte in plan inserate in structura, pentru cazul unidimensional folosim O(nr * log N) spatiu. Daca folosim structura hash_map sau map din STL obtinem o implementare foarte simpla si memoria folosita este putina.
In continuare, pentru exemplificarea folosirii stucturilor de date voi prezenta niste probleme care voiam sa le propun la concursul de programare Algoritmus, din pacate acest concurs s-a incheiat prematur pentru ca sponsorul nu a mai continuat finantarea premiilor pentru concurenti.
h2. Problema 1
Se dau $1<=n<=30 000$ triunghiuri dreptunghice in plan, ele se dau prin trei parametrii $x,y,m$. Varfurile triunghiurilor o sa fie ( $x, y$ ) ( $x + m, y$ ) si ( $x, y + m$ ). Sa se determine cate perechi de triunghiuri exista, astfel ca primul triunghi din pereche sa fie inclus in al doilea triunghi. ( $0<= x, y, m <= 60 000$ )
Timp de executie: $0.5 secunde$
Triunghiul determinat de parametrii ( $x{~1~},y{~1~},m{~1~}$ ) e inclus in triunghiul determinat de parametrii ( $x{~2~},y{~2~},m{~2~}$ ) daca si numai daca $x{~2~} <= x{~1~}$, $y{~2~} <= y{~1~}$ si $x{~1~} + y{~1~} + m{~1~} <= x{~2~} + y{~2~} + m{~2~}$. Deci daca facem transformarea ( $x{~1~}, y{~1~}, m{~1~}$ ) -> ( $x{~1~}, y{~1~}, -x{~1~} - y{~1~} - m{~1~}$ ) si notam cu ( $x{~1~}, y{~1~}, z{~1~}$) atunci avem ca triunghiul reprezentat de ( $x{~1~}, y{~1~}, z{~1~}$ ) e inclus in triunghiul reprezentat de ( $x{~2~}, y{~2~}, z{~2~}$ ) daca si numai daca $x{~2~} <= x{~1~}, y{~2~} <= y{~1~}, z{~2~} <= z{~1~}$. Astfel am transformat triunghiurile dreptunghice in puncte din spatiul 3D si perechile de triunghiuri cerute in problema in relatii de dominanta, pentru a afla cate triunghiuri includ triunghiul reprezentat de ( $x{~1~}, y{~1~}, z{~1~}$ ) trebuie sa vedem cate puncte sunt cuprinse in $(-oo, x{~1~}] x (-oo, y{~1~}] x (-oo, z{~1~}]$. Pentru a face acest lucru am putea folosi un arbore de intervale 3D care ocupa O(n log^2^ n) spatiu si are complexitatea O(log^3^ n) pentru query, dar observatia banala ca putem sorta sirul triunghiurilor dupa coordonata $z$ si abia apoi sa rezolvam problema ne va ajuta. Vom folosi un arbore de intervale 2D sau un _quadtree_ sau un 2D tree ({_kD tree_}) in care vom insera ( $x{~i~},y{~i~}$ ) in ordinea data de $z{~i~}$. Evident ca la momentul inserarii lui ( $x{~i~},y{~i~}$ ) in structura de date toate punctele deja inserate ( $x{~j~},y{~j~}$ ) vor proveni din un punct ( $x{~j~}, y{~j~}, z{~j~}$ ) cu $z{~j~} <= z{~i~}$, deci nu avem nevoie sa pastram coordonata $z$ a punctelor pentru comparatie. In cazul care implementam problema folosind {_kd trees_} vom avea complexitatea O(n log n) la crearea structurii de date si O(sqrt(n)) pentru query, memoria folosita va fi O(n), complexitatea totala a algoritmului O(n log n + n sqrt(n)). Daca folosim arbore de intervale atunci vom folosi O(n log n) timp la crearea structurii si vom avea O(log^2^ n) pentru query, memoria folosita va fi O(n log n), complexitatea totala va fi O(n log n + n log^2^ n). Daca folosim tehnica numita "fractional cascading" pentru arbori de intervale atunci reducem complexitatea la O(n log n) pentru intreaga problema.
O alta abordare a problemei bazata tot pe transformarea din triunghiuri in puncte in plan ar fi bazata pe metoda divide si stapaneste. Se impart punctele in doua multimi de dimensiuni egale dupa coordonata $z$, $n/2$ puncte au $z<=ZMID$ si celelalte $n-n/2$ puncte au $z>=ZMID$, dupa ce s-au numarat relatiile de dominanta din cele doua submultimi, trebuie sa gasim numarul de relatii de dominanta in care un punct e in prima multime si al doilea e in a doua multime. Evident oricare ar fi ( $x{~1~}, y{~1~}, z{~1~}$ ) in prima multime si ( $x{~2~}, y{~2~}, z{~2~}$ ) in a doua multime avem ca $z{~1~} <= ZMID <= z{~2~}$ deci mai trebuie sa verificam doar daca $x{~1~} <= x{~2~}$ si $y{~1~} <= y{~2~}$. Daca tinem sirul sortat dupa $y$ si folosim un arbore indexat binar pentru a insera coordonate $x$ in arbore atunci cand in sirul interclasat ordonat dupa $y$ intalnim un punct din prima multime inseram $x{~1~}$ in arborele indexat binar iar cand intalnim un punct din a doua multime atunci intrebam cate coordonate $x<=x{~2~}$ au fost deja inserate in arborele indexat binar daca $x <= x{~2~} => si y <= y{~2~}$ pentru ca a fost inserat in multime mai devreme, in total faza stapaneste a algoritmului ia O(n log n) timp pentru sortarea dupa $y$ si O(n log n) pentru inserarea in arborele indexat binar deci in totalitate algoritmul dureaza O(n log^2^ n).
A doua metoda poate fi extinsa la numararea incluziunilor de dreptunghiuri. Dreptunghiurile se vor transforma in puncte in 4D, iar cand vom fi la pasul de stapaneste din algoritm vom sorta dupa $z$ si ne va ramane sa determinam cate perechi $x{~1~} <= x{~2~}$ si $y{~1~} <= y{~2~}$, aceasta o vom rezolva folosind un arbore de intervale rafinat prin "fractional cascading", si astfel s-a pastrat complexitatea pasului stapaneste la O(n log n), deci complexitatea totala pentru dreptunghiuri ar fi O(n log^2^ n). Problema cu dreptunghiuri s-a dat la regionala ACM cu $N = 5 000$, atunci o singura echipa a rezolvat problema si solutia lor era O(N^2^).
Sa vedem care e complexitatea operatiei **cauta**. Nodurile care sunt total in afara dreptunghiului sau total inauntrul dreptunghiului Q pot cel mult fi de doua ori mai multe decat nodurile care intersecteaza dreptunghiul Q intr-o cautare, pentru ca vizitarea unui nod total in afara dreptunghiului sau unui nod dinauntrul dreptunghiului a pornit de la un nod al carui domeniu intersecteaza dreptunghiul. Pentru analiza ne putem ocupa numai de noduri ale caror domenii intersecteaza dreptunghiul. Pentru a obtine o limita superioara a numarului de zone intersectate putem considera numarul maxim de zone intersectate de o latura a dreptunghiului si sa inmultim acel numar cu patru. Pentru a mai simplifica analiza putem considera nu numarul maxim de zone intersectate de un segment, ci numarul maxim de zone intersectate de o dreapta verticala sau orizontala. Consideram o dreapta verticala, pentru un nod, daca directia de impartire a zonei asociate e verticala atunci dreapta verticala taie sau zona fiului stang sau zona fiului drept, dar nu pe amandoua deodata. Daca dreapta verticala nu intersecteaza zona asociata unui fiu atunci nu va mai intersecta zona nici unui urmas al fiului. In caz contrar intersecteaza ambii fii. Daca coboram la nivelul nepotilor cel mult patru noduri sunt intersectate. In cel mai rau caz intersectam domeniul reprezentat de radacina si putem intersecta cel mult $2^i^$ noduri pana la nivelul $2i$. Deci in total maxim O(sqrt(n)) noduri sunt parcurse la o operatie cauta.
