h1. Cautari ortogonale: Structuri de date si aplicatii

(Categoria _Structuri de date_, autor _Cosmin Negruseri_)

== include(page="template/implica-te/scrie-articole" user_id="alecman") ==
 
(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:

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.

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.

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.

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)$.

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^)$.

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

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

* 'Evantai':problema/evantai
* 'Schi':problema/schi

* 'Evantai':problema/cutii

* '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

h2. Bibliografie

[1] 'Arbori de intervale ("segment trees") si aplicaţii in Geometria Computationala ,Dana Lica':arbori-intervale
[2] 'Arbori Indexati Binar, Mihai Scortaru Ginfo': http://www.ginfo.ro/revista/13_1/focus.pdf

# '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

3692