Cautari ortogonale: Structuri de date si aplicatii

(Categoria Structuri de date, autor Cosmin Negruseri)

Introducere

In acest articol voi discuta despre cateva structuri de date folositoare pentru probleme de geometrie, in special pentru probleme ortogonale. Problema de baza ce va fi rezolvata suna in felul urmator: avem n puncte in plan si pentru un anumit dreptunghi ne intereseaza numarul de puncte din acel dreptunghi, sau diverse alte operatii pentru punctele din interiorul sau, cum ar fi suma cheilor punctelor, minimul sau maximul cheilor (daca punctele au asociate cate o cheie). Folosind arbori de intervale putem rezolva aceasta problema, dar vreau sa exemplific ce alte variante mai avem si avantajele lor, precum si aplicatii practice pentru cautarea pe domenii ortogonale. In general, abordarile prezentate mai jos se pot extinde de la cazul unidimensional sau bidimensional, cu usurinta, la cazuri N-dimensionale.
Pentru a intelege cat mai bine ideile si structurile de date prezentate mai departe recomand citirea articolelor [1] si [2].
Structurile prezentate sunt in general statice, adica formam intai structura si apoi rezolvam problema. Structurile de date se pot modifica pentru a suporta inserari si stergeri de puncte, devenind dinamice, dar astfel implementarea se complica. Pentru a simula dinamismul putem insera toate datele de la inceput si sa mai avem un camp boolean in care marcam cu true daca data a fost logic inserata si cu false daca data din nodul respectiv nu a fost inca logic inserata. Aceasta pastreaza complexitatea operatiilor pe structura si ne ajuta in echilibrarea structurilor pentru o eficienta buna a operatiilor.

QuadTree

QuadTree este o structura care organizeaza informatii pentru date multidimensionale, fiind folosita in cartografie, procesarea imaginilor, grafica pe calculator etc. Structura este un arbore ce reprezinta o zona din spatiul N-dimensional (in cazul in care suntem noi interesati, N=2), fiecare nod al arborelui pastreaza o informatie pentru o zona din spatiu, iar nodul are 2^N fii care reprezinta fiecare o zona de 2^N ori mai mica decat zona parintelui. Zonele fiilor sunt disjuncte, iar reuniunea lor formeaza zona parintelui.

Pentru un QuadTree radacina reprezinta un patrat, iar fii reprezinta cele patru patrate disjuncte si congruente in care se poate imparti patratul initial. Din cate am prezentat pana acum, un QuadTree este infinit, dar pe noi ne intereseaza de obicei intervale foarte mici din plan, si atunci putem sa folosim numai cateva nivele din QuadTree. Cateodata unele noduri din QuadTree nu contin insa nici o informatie si atunci nu avem nevoie sa le folosim pentru ca am folosi memorie in plus.

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.