Sejam w1 = (x, y) e w2 = (x′, y′) pontos no plano onde x < x′ e y < y′. Os segmentos de reta que formam um retˆangulo com os lados paralelos aos eixos s˜ao: s1 = (x, y)(x, y′), s2 = (x, y′)(x′, y′), s3 = (x′, y′)(x′, y) e s4 = (x′, y)(x, y). Uma janela W ´e formada pelos segmentos de reta de um retˆangulo e sua regi˜ao interna. Ao longo deste texto, usaremos alguns s´ımbolos de compara¸c˜ao. S˜ao eles: ≤x, >x, ≤y, >y. Usamos estes s´ımbolos para
2.2. PONTOS EM JANELAS - BIDIMENSIONAL 21
comparar dois pontos no plano. Dizemos que um ponto p ´e x-(menor ou igual) a um ponto q (p≤xq) se, e somente se, x(p) < x(q) ou (x(p) = x(q) e y(p)≤ y(q)). Um ponto p ´e x-maior que um ponto q se, e somente se, p n˜ao ´e x-(menor ou igual) a q. De forma an´aloga definimos quando um ponto ´e y-(menor ou igual) e y-maior que outro.
Uma ´arvore limite T constru´ıda sobre um conjunto de pontos no plano tem dois n´ıveis. A ´arvore do primeiro n´ıvel (ou ´arvore principal) ´e constru´ıda sobre as x-coordenadas dos pontos de P . Novamente, os pontos de P s˜ao armazenados nas suas folhas e os n´os internos armazenam pontos que direcionam uma busca no eixo x. Cada n´o da ´arvore principal aponta agora, adicionalmente, para uma estrutura associada que tamb´em ´e uma ´arvore de busca bin´aria balanceada. Denotamos por P (v) os pontos armazenados nas folhas da sub´arvore com raiz em um n´o v da ´arvore principal. A estrutura associada de v, ou seja, a ´arvore do segundo n´ıvel de v, ´e constru´ıda sobre os pontos de P (v). As suas folhas armazenam os pontos de P (v) e seus n´os internos armazenam pontos que orientam uma busca no eixo y. Uma estrutura associada a um n´o v de T ´e denotada por Ty(v). Um exemplo parcial de uma ´
arvore limite 2-n´ıveis pode ser visto na Figura 2.6.
p1 p1 p1 p2 p2 p2 p3 p3 p3 p3 p3 p4 p4 p4 p4 p4 p5 p5 p5 p5 p6 p6 p6 p7 p7 p7 p7 p8 p8 p8 v
Figura 2.6: Uma ´arvore limite 2-n´ıveis parcial.
Vamos falar mais sobre a constru¸c˜ao de uma ´arvore limite 2-n´ıveis. Considere um conjunto de pontos distintos no plano P e dois vetores ordenados sobre P . O primeiro vetor denotado por Vx= [p
1, p2, . . . , pn] ordenado de tal forma que p1<x p2<x . . . <xpn e o segundo vetor Vy = [q
1, q2, . . . , qn] tal que q1 <y q2 <y . . . <y qn. Dizemos que o vetor Vx est´a x-ordenado e que Vy est´a y-ordenado. Uma ´arvore limite 2-n´ıveis sobre P ´e constru´ıda recursivamente usando os vetores Vx e Vy da seguinte forma. Crie um n´o v e armazene nele o ponto p
⌈n2⌉. Construa a estrutura associada de v usando o vetor Vy. Construa dois vetores x-ordenados, Vx
e = [p1, p2, . . . , p⌈n2⌉] e Vdx = [p⌈n2⌉+1, p⌈n2⌉+2, . . . , pn] e dois vetores y-ordenados, Vey e Vdy, com os mesmos pontos em Vx
e e Vdxmas ordenados pela y-coordenada. A sub´arvore `a esquerda de v ´e constru´ıda da mesma forma usando os vetores Vex e V
y
e e a sub´arvore `a direita de v, usando os vetores Vx
d e V y
d. Conseguimos construir em tempo linear os vetores Vex, Vdx, V y e e Vdy percorrendo os vetores Vx e Vy. A constru¸c˜ao dos vetores Vx
e e Vdx ´e trivial. Os vetores Vey e Vdy podem ser constru´ıdos da seguinte forma. Para cada ponto q em Vy, compare a coordenada x de q com a de p⌈n
2⌉. Se q ≤x p⌈ n
2⌉ ent˜ao q pertence ao vetor V
x
e , e assim q ´e armazenado no vetor Vey. Caso contr´ario, q ´e armazenado no vetor Vdy. Considere a Figura
2.6 para interpretar a Figura 2.7.
O algoritmo Constroi ´ArvoreLimite descreve formalmente uma maneira de construir uma ´arvore limite 2-n´ıveis. Note que, se a linha 2 deste algoritmo consumir tempo linear ent˜ao a recorrˆencia que define o seu consumo de tempo ´e igual `a recorrˆencia da demonstra¸c˜ao do Lema 1. Com isso, o seu consumo de tempo ´e Θ(n log n).
Vx= [p 8, p6, p1, p2, p3, p7, p4, p5] Vx e = [p8, p6, p1, p2] Vy= [p 4, p1, p6, p3, p5, p8, p2, p7] Vx d = [p3, p7, p4, p5] Vy e = [p1, p6, p8, p2] Vdy= [p4, p3, p5, p7]
Figura 2.7: Os pontos do conjunto P (v) est˜ao representados nos vetores x-ordenado Vxe y-ordenado
Vy, os pontos do conjunto P (e(v)) nos vetores ordenados Vx
e e Vey e os pontos do conjunto P (d(v))
nos vetores ordenados Vx d e V
y d.
Algoritmo 6 Constroi ´ArvoreLimite(vetor Vx, vetor Vy)
Entrada: Um conjunto de pontos distintos n˜ao vazio P atrav´es de dois vetores: um x- ordenado Vx = [p
1, p2, . . . , pn] e outro y-ordenado Vy = [q1, q2, . . . , qn]. Sa´ıda: A raiz v de uma ´arvore limite 2-n´ıveis.
1. Crie um n´o v.
2. Ty(v)← ConstroiEstruturaAssociada(Vy)
3. Crie quatro vetores vazios: Vex, Vdx, Vey e Vdy
4. Vex ← [p1, p2, . . . , p⌈n 2⌉]. 5. Vx
d ← [p⌈n2⌉+1, p⌈n2⌉+2, . . . , pn].
6. para i← 1 at´e n fa¸ca
7. se qi ≤xp⌈n
2⌉ ent˜ao
8. Insira no final do vetor Vey o ponto qi.
9. sen˜ao
10. Insira no final do vetor Vdy o ponto qi.
11. fim se
12. fim para
13. p(v)← p⌈n 2⌉
14. se Vx cont´em um ´unico ponto ent˜ao
15. Marque v como folha.
16. sen˜ao
17. e(v)← Constroi ´ArvoreLimite(Vx e, V y e) 18. d(v)← Constroi ´ArvoreLimite(Vdx, Vdy) 19. fim se 20. devolva v
2.2. PONTOS EM JANELAS - BIDIMENSIONAL 23
Falta ent˜ao, descrever como constru´ımos uma estrutura associada de um n´o v de T . Ela deve ser uma ´arvore de busca bin´aria. Podemos constru´ı-la baseados na ideia de constru¸c˜ao de heap. Os membros de cada n´o u desta ´arvore s˜ao:
• um ponto, p(u); e
• o ponto armazenado na folha mais `a direita do seu filho `a direita, que vamos denotar por pd(u).
Como na ´arvore principal, p(u) ´e usado para orientar uma busca. J´a pd(u) ´e uma informa¸c˜ao usada durante sua constru¸c˜ao. Para garantir um consumo de tempo linear, vamos construir Ty usando uma estrat´egia “de baixo para cima”.
Seja P um conjunto com n pontos distintos. Sejam l o n´umero de folhas do ´ultimo n´ıvel h e l′ o n´umero de folhas do pen´ultimo n´ıvel h− 1 de Ty. Como o n´umero de folhas ´e n temos que, l + l′= n. Sabemos que, ao somar l com 2l′ teremos o n´umero m´aximo de n´os no n´ıvel h, ou seja, l + 2l′= 2h. Resolvendo este sistema, encontramos o n´umero de folhas nos n´ıveis h− 1 (l′ = 2h− n) e h (l = n − l′). O valor de h ´e dado pelo primeiro n´ıvel de T
y tal que o seu n´umero de n´os ´e maior ou igual a n, ou seja, h ´e o menor inteiro tal que 2h ≥ n. Mais precisamente, h =⌈log n⌉. h tamb´em ´e a altura de Ty.
Pelo Lema 3 sabemos que o n´umeros de n´os da ´arvore Ty ´e N = 2n − 1. Com as informa¸c˜oes: o n´umero de n´os; o n´umero de folhas em h; e o n´umero de folhas em h− 1, podemos efetivamente construir Ty come¸cando pelas suas n folhas. Suponha que os pontos de P est˜ao armazenados em um vetor y-ordenado Vy = [q
1, q2, . . . , qn]. Os pontos armazenados nas l folhas do n´ıvel h s˜ao os l primeiros pontos do vetor Vy, ou seja, q
1, q2, . . . , ql. Eles devem ser armazenados nas l ´ultimas posi¸c˜oes de Ty. Os pontos armazenados nas l′ folhas restantes s˜ao os l′ pontos restantes de Vy, q
l+1, ql+2, . . . , qn. Eles devem ser armazenados nas posi¸c˜oes que antecedem as l ´ultimas posi¸c˜oes do vetor. Note que, ao percorremos as folhas da ´
arvore Ty da esquerda para a direita temos uma y-ordena¸c˜ao dos pontos nelas armazenados. O exemplo da Figura 2.9 ilustra o preenchimento das folhas.
Completando a constru¸c˜ao, para cada n´o interno u de Ty, p(u) = pd(e(u)) e pd(u) = pd(d(u)). Os primeiros n´os internos a serem constru´ıdos est˜ao no n´ıvel h− 1. Em seguida, constru´ımos os n´os do n´ıvel h− 2, e assim por diante. Perceba que, a manuten¸c˜ao de pd(u) ´e importante, pois, se u ´e filho `a esquerda de um n´o v, ent˜ao p(v) deve ser igual a pd(u). Veja como fica a estrutura Ty da Figura 2.9 na Figura 2.10 depois de completada sua constru¸c˜ao.
Lema 5 Uma estrutura associada Ty ´e uma ´arvore de busca bin´aria com altura O(log n).
Demonstra¸c˜ao: Vamos mostrar que uma estrutura constru´ıda como descrevemos acima ´e uma ´
arvore de busca bin´aria, mostrando que o ponto armazenado em qualquer n´o da estrutura ´e y-(maior ou igual) a um ponto armazenado em qualquer n´o da sua sub´arvore `a esquerda e y-menor que um ponto armazenado em qualquer n´o da sua sub´arvore `a direita.
Seja u um n´o de uma estrutura associada Ty. Sejam ue e ud dois n´os descendentes `
a esquerda e `a direita de u, respectivamente. Pela constru¸c˜ao, p(u) = pd(e(u)), p(ue) = pd(e(ue)) e p(ud) = pd(e(ud)) e pd(e(u)), pd(e(ue)) e pd(e(ud)) s˜ao pontos armazenados em uma folha de Ty. Ent˜ao temos que mostrar que pd(e(ue)) ≤y pd(e(u)) <y pd(e(ud)). Pela y-ordena¸c˜ao das folhas ´e direto perceber isso (veja a Figura 2.8). Logo, a estrutura associada ´e uma ´arvore de busca bin´aria. Pela sua constru¸c˜ao, h =⌈log n⌉ e assim ela ´e balanceada.
u u pd(e(u)) pd(e(u)) ue ud pd(e(ue)) pd(e(ue)) e(ue) e(ud) e(u) e(u)
Figura 2.8: Pela y-ordena¸c˜ao das folhas temos que pd(e(ue)) = p(ue) ≤y pd(e(u)) = p(u) <y
pd(e(ud)) = p(ud). Vy = {p9, p4, p1, p6, p3, p5, p8, p2, p7} h =⌈log 9⌉ = 4 l′= 7 l = 2 Ty p1 p1 p1p1 p2 p2 p2 p2 p3 p3 p3 p3 p4 p4 p4 p4 p5 p5 p5 p5 p6 p6 p6 p6 p7 p7 p7 p7 p8 p8 p8 p8 p9 p9 p9 p9 8 9 10 11 12 13 14 15 16 p(u) u pd(u)
Figura 2.9: Preenchimento das folhas de uma estrutura associada, Ty, baseada em heap. Perceba que
as folhas do n´ıvel h s˜ao filhas dos n´os internos mais `a esquerda do n´ıvel h− 1.
O algoritmo ConstroiEstruturaAssociada constroi tal ´arvore. Note que as linhas 8 – 12 e 15 – 19 juntas executam n vezes. As linhas 7 e 14 executam no total duas vezes mais, ou seja, n + 2. Nas linhas 11 e 18 a vari´avel i ´e decrementada. Como i possui inicialmente valor igual a 2n − 1 teremos na primeira itera¸cao do enquanto da linha 21 i com valor n− 1. Com isso, as linhas 22 – 25 s˜ao executadas n − 1 vezes e a linha 21 ´e executada
2.2. PONTOS EM JANELAS - BIDIMENSIONAL 25 p1 p1 p1 p1 p1p1 p2 p2 p2 p2p2 p3 p3 p3 p3 p3 p3p3 p4 p4 p4 p4 p4p4 p5 p5 p5 p5p5 p6 p6 p6 p6p6 p7 p7 p7 p7 p7p7 p8 p8 p8 p8 p8p8 p9 p9 p9 p9p9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Figura 2.10: Ty totalmente preenchida. Est´a ilustrado em cada n´o v da ´arvore somente os pontos que
orientam uma busca, ou seja, p(v). Em cada n´o v do vetor ilustramos p(v) e pd(v).
n vezes. Como toda linha consome tempo constante, o consumo de tempo do algoritmo ConstroiEstruturaAssociada´e Θ(n).
Passada a fase de pr´e-processamento, mostraremos como responder a uma consulta. Seja T uma ´arvore limite 2-n´ıveis constru´ıda sobre um conjunto de pontos distintos P com cardi- nalidade igual a n. Uma W -consulta sobre P devolve todos os pontos pertencentes a P que est˜ao em W . ´E importante notar que a ´arvore principal de T orienta uma busca no eixo x e cada estrutura associada orienta uma busca sobre o eixo y. Realizamos uma W -consulta sobre P da seguinte forma. Primeiramente, encontramos o n´o mais alto de T , vdiv, tal que w1 ≤x p(vdiv) <x w2. Isso ´e feito chamando EncontraN´oDivide(raiz(T ), W ). Uma pe- quena altera¸c˜ao deve ser feita neste algoritmo. Os s´ımbolos ≤ e > devem ser trocados por ≤x e >x. Assim, p(vdiv) est´a na ´area hachurada mostrada na Figura 2.11.
00000 00000 00000 00000 00000 00000 11111 11111 11111 11111 11111 11111 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 00000 00000 00000 00000 00000 00000 00000 00000 00000 11111 11111 11111 11111 11111 11111 11111 11111 11111 W w1 w2
Algoritmo 7 ConstroiEstruturaAssociada(vetor Vy)
Entrada: Um conjunto de pontos distintos n˜ao vazio P atrav´es de um vetor y-ordenado Vy = [q
1, q2, . . . , qn].
Sa´ıda: Uma estrutura associada sobre P .
1. Crie um vetor Ty com 2n− 1 posi¸c˜oes.
2. h← ⌈log(n)⌉
3. l′ ← 2h− n
4. l← n − l′ 5. i← 2n − 2
6. ⊲ Nas linhas 7 – 12 constru´ımos as folhas do n´ıvel h.
7. para j← l − 1 decrescendo at´e 0 fa¸ca 8. p(Ty[i])← Vy[j]
9. pd(Ty[i])← Vy[j]
10. Marque Ty[i] como folha.
11. i← i − 1
12. fim para
13. ⊲ Nas linhas 14 – 19 constru´ımos as folhas do n´ıvel h− 1. 14. para j← n − 1 decrescendo at´e l fa¸ca
15. p(Ty[i])← Vy[j]
16. pd(Ty[i])← Vy[j]
17. Marque Ty[i] como folha.
18. i← i − 1
19. fim para
20. ⊲ Nas linhas 21 – 25 constru´ımos os n´os internos.
21. enquanto i≥ 0 fa¸ca 22. p(Ty[i])← pd(Ty[2i + 1]) 23. pd(Ty[i])← pd(Ty[2i + 2]) 24. i← i − 1 25. fim enquanto 26. devolva Ty
Em seguida, percorremos as sub´arvores `a esquerda e `a direita de vdiv buscando pelos pontos w1 e w2, respectivamente. Vamos falar como obtemos os pontos que est˜ao em W e armazenados nas folhas da sub´arvore `a esquerda de vdiv. Os pontos armazenados na sub´arvore `
a sua direita s˜ao obtidos de forma semelhante. Pela constru¸c˜ao de T , a sub´arvore `a esquerda de vdiv armazena pontos de P que s˜ao x-(menores ou iguais) a p(vdiv). Logo, eles s˜ao x- menores que w2. Suponha que estamos em um n´o v descendente `a esquerda de vdiv. Se w1 >x p(v), ent˜ao nada podemos fazer a n˜ao ser continuar a busca na sub´arvore com raiz em d(v). No entanto, se w1 ≤x p(v) ent˜ao a busca continua na sub´arvore com raiz em e(v) e w1 <x p(r) <x w2, para todo ponto r armazenado na sub´arvore com raiz em d(v). Sabemos que Ty(d(v)) armazena tais pontos. Logo, de forma sim´etrica, encontramos em Ty(d(v)) o n´o mais alto v′div tal que w1 ≤y p(vdiv′ ) <y w2 chamando EncontraN´oDivide(raiz(Ty(d(v))), W )
2.2. PONTOS EM JANELAS - BIDIMENSIONAL 27
com os s´ımbolos ≤ e > modificados para ≤y e >y. Percorremos as sub´arvores `a esquerda e `
a direita de v′div buscando pelos pontos w1 e w2 e encontramos alguns pontos que est˜ao em W . Veja a Figura 2.12. 00 00 00 00 11 11 11 11 000 000 000 000 000 000 000 000 000 111 111 111 111 111 111 111 111 111 0 0 0 0 0 0 1 1 1 1 1 1 w1<xp(r) <xw2 w1≤xp(v) v vdiv Ty(d(v)) v′ div
Figura 2.12: Os pontos nas ´arvores hachuradas est˜ao em W .
As buscas por w1 e w2, tanto na ´arvore principal quanto em uma estrutura associada, continuam at´e atingirem uma folha f . Por fim, verificamos se p(f ) pertence a W . Mais detalhes s˜ao encontrados no algoritmo Consulta ´ArvoreLimite. Ele chama o algoritmo Consulta ´ArvoreLimite1D que deve ter os s´ımbolos ≤ e > alterados para ≤y, e >y. Lema 6 [4, 18, 19, 29] O algoritmo Consulta ´ArvoreLimite realiza uma W -consulta sobre um conjunto de pontos distintos P em tempo O(log2n + k), onde n ´e o n´umero de pontos de P e k ´e o n´umero de pontos de P que est˜ao na janela W .
Demonstra¸c˜ao: Seja T uma ´arvore limite 2-n´ıveis constru´ıda sobre P . Sabemos que consu- mimos tempo O(log n) para encontrar o n´o vdiv em T . As buscas por w1 e w2 nas sub´arvores `
a esquerda e `a direita de vdiv produzem dois caminhos Cx e Cx′ com comprimento O(log n), pois T ´e balanceada. Para cada n´o v de Cx ou Cx′, possivelmente chamamos o algoritmo Consulta ´ArvoreLimite1Dpassando como parˆametro a estrutura associada do n´o d(v) ou e(v). Pelo Lema 4, o consumo de tempo de cada chamada ´e O(log n+kv), onde kv ´e o n´umero de pontos armazenados nas sub´arvores com raiz em d(v) ou e(v) que est˜ao em W . Como a soma dos kv’s ´e igual a k, segue que o consumo de tempo do algoritmo ´e O(log2n + k). Conseguimos melhorar o consumo de tempo de uma W -consulta sobre um conjunto de pontos distintos P se usarmos uma t´ecnica chamada cascateamento fracion´ario, tema da nossa pr´oxima se¸c˜ao.
Algoritmo 8 Consulta ´ArvoreLimite(´arvore limite vraiz, janela W )
Entrada: Um conjunto de pontos distintos n˜ao vazio P armazenados em uma ´arvore limite 2-n´ıveis T com raiz no n´o vraiz e uma janela W .
Sa´ıda: Uma lista L que cont´em os pontos de P que pertencem a W .
1. L← ∅
2. vdiv ← EncontraN´oDivide(vraiz, W )
3. se vdiv ´e uma folha ent˜ao
4. ⊲ Verifique se o ponto associado `a folha vdiv deve ser armazenado em L.
5. se w1≤xp(vdiv)≤xw2 e w1 ≤y p(vdiv)≤y w2 ent˜ao
6. L← {p(vdiv)}
7. fim se
8. sen˜ao
9. ⊲ Ande no caminho Cx.
10. v← e(vdiv)
11. enquanto v n˜ao ´e uma folha fa¸ca
12. se w1 ≤x p(v) ent˜ao
13. ⊲ Verifique a y-coordenada dos pontos armazenados na sub´arvore com raiz em Ty(d(v)). 14. L← L ∪ Consulta ´ArvoreLimite1D(Ty(d(v)), W ) 15. v← e(v) 16. sen˜ao 17. v← d(v) 18. fim se 19. fim enquanto
20. ⊲ Verifique se o ponto associado `a folha v deve ser armazenado em L.
21. se w1≤xp(v)≤x w2 e w1≤y p(v)≤y w2 ent˜ao
22. L← L ∪ {p(v)}
23. fim se
24. ⊲ Ande no caminho Cx′. 25. v← d(vdiv)
26. enquanto v n˜ao ´e uma folha fa¸ca
27. se w2 >x p(v) ent˜ao
28. ⊲ Verifique a y-coordenada dos pontos armazenados na sub´arvore com raiz em Ty(e(v)).
29. L← L ∪ Consulta ´ArvoreLimite1D(Ty(e(v)), W )
30. v← d(v)
31. sen˜ao
32. v← e(v)
33. fim se
34. fim enquanto
35. ⊲ Verifique se o ponto associado `a folha v deve ser armazenado em L. 36. se w1≤xp(v)≤x w2 e w1≤y p(v)≤y w2 ent˜ao
37. L← L ∪ {p(v)}
38. fim se 39. fim se