Pentru a reprezenta $n$ puncte de coordonate intregi in plan cu ajutorul structurii de _QuadTree_, vom insera care un punct pe rand in _QuadTree_. Pornim de la un _QuadTree_ gol si inseram un nod recursiv, vedem pentru fiecare patrat care nu are latura de dimensiune unu in care din cele patru patrate din interiorul lui intra punctul nostru. Daca nu exista nod care sa reprezinte acel patrat, il creem noi.
Avantajul pentru structura de _QuadTree_ este usurinta implementarii, dezavantajul este ca structura lui si timpul de raspuns la intrebari depind si de configuratia punctelor, nu numai de numarul total de puncte.
Avantajul pentru structura de _QuadTree_ este usurinta implementarii, dezavantajul este ca structura lui si timpul de raspuns la intrebari depind si de configuratia punctelor, nu numai de numarul total de puncte.
h2. kD-Tree
_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:
== code(cpp) |
Nod-kD construiesteArbore(puncte, directie)
daca puncte e vida returneaza null
altfel daca puncte contine un singur punct returneaza Nod-kD(puncte[0])
altfel
x = gasesteMediana(puncte, directie)
// aceasta functie poate fi implementata folosind selectie randomizata
stanga = puncte cu directie <= x;
dreapta = puncte cu directie > x;
t = Nod-kD(x)
t.stanga = construiesteArbore(stanga, (directie + 1) % 2);
t.dreapta = construiesteArbore(dreapta, (directie + 1) % 2);
returneaza t
==
Pentru a nu face de fiecare data selectie randomizata putem pleca de la inceput cu doua liste de puncte, una sortata dupa $x$ si cealalta sortata dupa $y$.
Pseudocod pentru cautare pe domeniu ortogonal (Notam cu Q un dreptunghi):
== code(cpp) |
puncte cauta(nod-kD, Q)
daca Q intersectat cu Nod-kD.domeniu e vid atunci returneaza multimea vida
altfel daca Nod-kD.domeniu e inclus in Q atunci
returneaza punctele din subarborele cu radacina nod-kD
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^)$.
h2. Problema 2
Se dau doua multimi de puncte de coordonate intregi in plan cu $N$ si $M$ puncte. Punctele din prima multime sunt colorate rosu si punctele din a doua multime sunt colorate albastru. Se cere sa se determine o pereche de puncte, unul rosu si unul albastru, intre care distanta manhattan e minima. Coordonatele punctelor sunt cuprinse intre $0$ si $60 000$. $1 <= M <= 30 000$ si $1 <= N <= 30 000$
Timp de executie: $0.5 secunde$
Pentru fiecare punct rosu vrem sa stim punctul albastru cel mai apropiat, impartim planul in 4 cadrane cu originea in punctul rosu, vrem sa aflam punctul albastru cel mai apropiat din fiecare cadran. Pentru un punct rosu si un punct albastru din cadranul 1 distanta dintre ele e $(x{~a~} - x{~r~}) + (y{~a~} - y{~r~})$ pentru ca $x{~r~} < x{~a~}$ si $y{~r~} < y{~a~}$, regrupand avem $(x{~a~} + y{~a~}) - (x{~r~} + y{~r~})$. Deci vrem sa gasim punctul $(x{~a~}, y{~a~})$ cu proprietatea ca $x{~r~} <= x{~a~}$ si $y{~r~} <= y{~a~}$ si suma $x{~a~} + y{~a~}$ e minima. O solutie ar fi sa folosim un arbore de intervale bidimensional, dar observam ca ambele margini pe domeniul pe care cautam sunt infinite, deci am putea sorta sirurile de puncte descrescator dupa $x$. Cand punctul $(x,y)$ e albastru inseram in arborele indexat binar la pozitia $y$ cheia $x+y$, iar cand punctul este rosu facem un query al elementului minim pe intervalul $[y, +oo)$ (evident toate punctele deja inserate in arbore au ordonata mai mare decat $y$-ul actual). Facem la fel pentru fiecare din cele patru cadrane.
h2. Problema 3
Se dau $1<= N <= 50 000$ de dreptunghiuri in plan si se cere sa se determine numarul de perechi de dreptunghiuri care se intersecteaza. Coordonatele varfurilor dreptunghiurilor sunt intregi si cuprinse intre $0$ si $60 000$.
Timp de executie: $0.5 secunde$
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. Problema 4
Se dau $1<= N <= 60 000$ de dreptunghiuri in plan, sa se determine un punct care are proprietatea ca este inclus in un numar maxim de dreptunghiuri. Coordonatele varfurilor dreptunghiurilor sunt cuprinse intre $0 si 60 000$.
Timp de executie: $0.5 secunde$
Reducem problema din plan pe dreapta, daca se da o multime de segmente pe o linie cum determinam un punct care e acoperit de numar maxim de segmente? O sortare a segmentelor dupa primul capat ar rezolva problema, dar solutia aceasta nu e flexibila daca vrem sa adaugam sau sa stergem segmente. Vom folosi un arbore de intervale unidimensional. Numim acoperire canonica a unui interval, intervalele asociate lui in arborele de intervale (stim din articolul [1] ca numarul acestor intervale este maxim $log n$). In nodurile arborelui de intervale pastram doua atribute: $nr$ si $max$, $nr$ reprezinta numarul de intervale pentru care intervalul asociat nodului face parte din acoperirea canonica, iar $max$ reprezinta intersectia de intervale nevida inclusa strict in intervalul asociat nodului, cu cardinal maxim. Pentru un nod $x$, $x.max$ e egal cu maximul dintre $x.stanga.max + x.stanga.nr$ sau $x.dreapta.max + x.dreapta.nr$. La inserarea sau stergerea din arbore a unui interval avem grija la actualizarea atributelor $max$ si $nr$. Pentru a determina numarul maxim de segmente ce se intersecteaza putem returna $radacina.nr + radacina$.
Acum ca putem rezolva problema pe dreapta in mod dinamic sa revenim la problema initiala in plan, vom folosi din nou paradigma liniei de baleiere. Folosim numai segmentele verticale si le ignoram pe cele orizontale. Sortam segmentele verticale dupa $x$ si cand intalnim un segment vertical ce a fost initial latura stanga de dreptunghi atunci adaugam acest segment in arborele de intervale si actualizam daca e nevoie cardinalul intersectiei maxime, daca intalnim un segment vertical care initial era latura din dreapta a unui dreptunghi atunci scoatem acest segment din arborele de intervale. Solutia problemei va avea complexitate $O(n log n)$, $O(n log n)$ in faza de sortare a segmentelor si $O(n log n)$ in faza de inserare in arbore si stergere din arbore.
h2. Alte probleme propuse spre rezolvare
* 'Evantai':problema/evantai
* 'Schi':problema/schi
* 'Cutii':problema/cutii
* 'Order':problema/order
* 'Nestable':http://www.topcoder.com/stat?c=problem_statement&pm=1986
* 'Mobiles':http://olympiads.win.tue.nl/ioi/ioi2001/contest/day1/mobiles/mobiles.pdf
* 'ZJU 2112':http://acm.zju.edu.cn/show_problem.php?pid=2112
* 'ZJU 2118':http://acm.zju.edu.cn/show_problem.php?pid=2118
* 'ZJU 2119':http://acm.zju.edu.cn/show_problem.php?pid=2119
* 'Wys':http://www.oi.edu.pl/php/show.php?ac=e180811&module=show&file=zadania/oi11/wys
* 'MIPT 43':http://acm.mipt.ru/judge/bin/problems.pl?problem=043&sort=ID&lang=en
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
# 'Kd-Trees, Andrew W. Moore':http://www.autonlab.org/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en
