Búsqueda de Rango Ortogonal - CINVESTAVertello/gc/sesion14.pdf · Introducción Consultas de Rango Ortogonal Consultas de Rango Ortogonal A primera vista parece ser que las bases

Búsqueda de Rango Ortogonal

Pedro RetaAuraham Camacho

CINVESTAV-Tamaulipas

8 de marzo del 2013

(CINVESTAV) Búsqueda de Rango Ortogonal 8 de marzo del 2013 1 / 102

1 Introducción

2 Búsqueda de Rango Ortogonal

3 Range Trees

4 Higher-Dimensional Range Trees

5 General Set of Points

6 Fractional Cascading


Introducción Consultas de Rango Ortogonal

Consultas de Rango Ortogonal

El material de la clase de hoy está basado en el capítulo 5 delsiguiente libro:Mark de Berg, Otfried Cheong, Marc van Kreveld and MarkOvermars. Computational Geometry: Algorithms and Applications.Springer, 3rd edition (April 16, 2008), ISBN-10: 3540779736.




A primera vista parece ser que las bases de datos tienen pocarelación con geometría.

Sin embargo, muchos tipos de preguntas o queries pueden serrepresentados geométricamente.

Para este fin, se puede realizar la siguiente transformación:

registros → puntosconsultas sobre registros → consultas sobre puntos




Considere una base de datos para el manejo de personal.

Se desea consultar a todos los empleados que:

Nacieron entre 1950 y 1955Ganen entre $3 000 y $4 000

Para representar esto como un problema geométrico,representamos cada empleado como un punto en el plano.

De esta forma, la consulta geométrica consiste en reportar todos lospuntos en el plano que cumplan los criterios anteriores.




Figura: Interpretando una consulta geométricamente (2D)




Ahora, considere agregar otro criterio de búsqueda, el número dehijos por empleado.

Se desea consultar a todos los empleados que:

Nacieron entre 1950 y 1955Ganen entre $3 000 y $4 000Tengan entre 1 y 2 hijos.

Para representar esto como un problema geométrico,representamos cada empleado como un punto en el espacio.

De esta forma, la consulta geométrica consiste en reportar todos lospuntos en el espacio que cumplan los criterios anteriores.




Figura: Interpretando una consulta geométricamente (3D)




En general, si estamos interesados en responder consultas sobre dcampos de un registro se debe efectuar la siguientetransformación:

registros → puntos en un espacio d-dimensional

De igual forma, una consulta sobre registros se tranforma a unaconsulta sobre puntos que se encuentran dentro de una cajaparalela a los ejes de un espacio d-dimensional.

A este tipo de consultas se les conoce como consultas de rangorectangular o consultas de rango ortogonal en geometríacomputacional.


Búsqueda de Rango Ortogonal Búsqueda de Rango 1-Dimensional

2 Búsqueda de Rango OrtogonalBúsqueda de Rango 1-DimensionalEjemploNodo de bifurcación vsplitAlgoritmo 1DRangeQueryKd-TreesAlgoritmo BuildKdTreeComplejidadRegión de un nodo



Búsqueda de Rango 1-Dimensional

Antes de analizar búsquedas en 2 dimensiones o más, veamos elcaso 1-dimensional.

Los datos serán representados como un conjunto P de puntos enun espacio 1-dimensional, es decir, números reales sobre la recta.

P = {p1, p2, ..., pn}

Una consulta reporta los puntos dentro de un rectángulo1-dimensional, es decir, un intervalo [x : x′].




Es posible resolver el problema de búsqueda 1-dimensionalusando un árbol de búsqueda balanceado T donde:

Los nodos hoja representan los puntos de PLos nodos internos representan valores de división para guiar labúsqueda.

Denotamos el valor de división almacenado en el nodo v como xv.

Asumimos que el subárbol a la izquierda de v contiene valoresmenores o iguales a v y que el subárbol a la derecha de v contienevalores mayores a v.




Figura: Árbol balanceado de búsqueda




Para reportar todos los puntos en una búsqueda de rango [x : x′] seprocede como sigue.

Sean µ y µ′ los nodos hoja en donde termina la búsqueda

Entonces, los puntos en el intervalo [x : x′] son aquellas hojas entreµ y µ′ 1.

1µ y µ′ pueden ser límites inclusivos o exclusivos(CINVESTAV) Búsqueda de Rango Ortogonal 8 de marzo del 2013 14 / 102

Búsqueda de Rango Ortogonal Ejemplo




Ejemplo

Se desean conocer los puntos en el rango [18 : 77] dentro de unárbol.

Estos puntos serán nodos hoja que pertencen a ciertos subárboles(gris oscuro) en el camino de búsqueda (gris claro).



Ejemplo

Figura: Búsqueda de rango 1-dimensional



Ejemplo

Por lo tanto, se deben realizar dos tareas:

Encontrar un nodo de bifurcación vsplit que divida el camino debúsqueda (color verde).Encontrar los nodos dentro del rango [x : x′].


Búsqueda de Rango Ortogonal Nodo de bifurcación vsplit




Nodo de bifurcación vsplit

Sean lc(v) y lr(v) los hijos a la izquierda y derecha,respectivamente, de un nodo v.

El siguiente algoritmo permite encontrar el nodo vsplit.



Nodo de bifurcación vsplit

Require: Un árbol T y dos valores x y x′ donde x ≤ x′ .Ensure: El nodo v donde las ramas hacia x y x′ se dividen o la hoja donde ambas ramas

terminan.

function FINDSPLITNONE(T , x, x′)v← root(T )while v no es hoja and (x′ ≤ x or x > xv) do

if x′ ≤ x thenv← lc(v)

elsev← lr(v)

return v


Búsqueda de Rango Ortogonal Algoritmo 1DRangeQuery




Algoritmo 1DRangeQuery

Enseguida, hace falta reportar aquellos puntos que se encuentrandentro del rango establecido.

Para esto, hacemos uso de vsplit para guiar la búsqueda.

El siguiente algoritmo realiza el recorrido por la izquierda delárbol, siendo similar para la búsqueda por la derecha.




Require: Un árbol T y dos valores x y x′ donde x ≤ x′ .Ensure: El nodo v donde las ramas hacia x y x′ se dividen o la hoja donde ambas ramas

terminan.function 1DRANGEQUERY(T , [x : x′])

vsplit ← FINDSPLITNODE(T , x, x′))if vsplit es hoja then

Verificar si vsplit se debe reportarelse

v← lc(vsplit)while v no sea hoja do

if x ≤ xv thenReportSubtree(rc(v))v← lc(v)

elsev← rc(v)

Verificar si vsplit se debe reportarSimilarmente, recorrer el camnio hacia x′Reportar los puntos en los subárboles izquierdos




v x ≤ xv




v x ≤ xv

23 18 ≤ 23




v x ≤ xv

23 18 ≤ 2310 18 � 10




v x ≤ xv

23 18 ≤ 2310 18 � 1019 18 ≤ 19




v x ≤ xv

23 18 ≤ 2310 18 � 1019 18 ≤ 1923 18 ≤ 23


Búsqueda de Rango Ortogonal Kd-Trees




Kd-Trees

Ahora revisemos el caso 2D.

Sea P un conjunto de n puntos en el plano. Se asume que lospuntos están en posición general.

Una consulta de rango rectangular 2-dimensional sobre P reportaaquellos puntos dentro del rectángulo formado por[x : x′]× [y : y′].



Kd-Trees

Un punto p = (px, py) se encuentra dentro de [x : x′]× [y : y′] si ysólo si:

px ∈ [x : x′] y py ∈ [y : y′]



Kd-Trees

En el caso 1-dimensional el árbol binario de búsqueda se crea apartir de un solo valor, la coordenada x.

En el caso 2-dimensional este árbol se debe crear considerandodos coordenadas.

Una forma de crear el árbol consiste en dividir el plano ensubconjuntos (mitades) sucesivamente. El procedimiento es elsiguiente.



Kd-Trees

Se divide el conjunto P en dos subconjuntos de aproximadamenteel mismo tamaño con una línea l, la cual se almacena en la raíz deT .

Se obtienen dos subconjuntos:

Pleft contiene aquellos puntos a la izquierda o sobre lPright contiene aquellos puntos a la derecha de l

Enseguida, se divide de nuevo los conjuntos anteriores, peroahora con una línea horizontal.

A medida que se dividen los subconjuntos, aumenta el nivel deprofundidad el cual llamaremos depth. Veamos un ejemplo.



Kd-Trees

depth = 0(CINVESTAV) Búsqueda de Rango Ortogonal 8 de marzo del 2013 35 / 102


Kd-Trees

depth = 1



Kd-Trees

depth = 2



Kd-Trees

depth = 3



Kd-Trees

En general, la división del plano se realiza de esta manera:

Se divide con una línea vertical si la profundidad es parSe divide con una línea horizontal si la profundidad es impar

Al reorganizar los nodos se obtiene el siguiente árbol.



Kd-Trees



Kd-Trees

A un árbol como este se le conoce como árbol-kd o kd-tree.

Es posible crear un árbol-kd a partir de un conjunto de puntos P yun nivel de profundidad o recursión.

El nivel de profundidad será de utilidad para determinar si sedebe dividir a P con una línea horizontal o vertical.


Búsqueda de Rango Ortogonal Algoritmo BuildKdTree




Algoritmo BuildKdTree

A continuación se muestra el algoritmo para la creación de unárbol-kd.

Note que está basado en un enfoque divide y vencerás.



Algoritmo BuildKdTree

Require: Un conjunto de puntos P y una profundidad depthEnsure: La raíz de un árbol-kd almacenando P

function BUILDKDTREE(P, depth)if P contiene sólo un punto then

return una hoja con este puntoelse

if depth es par thenDividir P en dos subconjuntos con una línea vertical lSea P1 el conjunto de puntos a la izquierda o en lSea P2 el conjunto de puntos a la derecha de l

elseDividir P en dos subconjuntos con una línea horizontal lSea P1 el conjunto de puntos abajo o en lSea P2 el conjunto de puntos arriba de l

vleft ← BUILDKDTREE(P1, depth + 1)vright ← BUILDKDTREE(P2, depth + 1)Crear un nodo v que almacene lColocar vleft a la izquierda de vColocar vright a la derecha de vreturn v


Búsqueda de Rango Ortogonal Complejidad




Complejidad

Existen básicamente dos tareas relevantes en el algoritmo:

División del conjunto consiste en dividir P en P1 y P2 a partir dela mediana. Si P se encuentra ordenado el proceso de encontrar elpunto de división será más simple. Esto tomará un tiempoO(n log(n)).

Unión de resultados consiste en agregar los subárboles vleft yvright a la raíz v. Esto se puede realizar en tiempo O(n).



Complejidad

Por lo tanto, la complejidad del algoritmo se resume a la siguienterelación de recurrencia:

T(n) =

{O(1) if n = 1O(n) + 2T(dn

2e) if n > 1.

Siendo esto igual a O(n log(n))


Búsqueda de Rango Ortogonal Región de un nodo




Región de un nodo

La región correspondiente a un nodo v es un rectángulo, el cualpuede ser abierto en uno o más lados.

Denotamos esta región como region(v).



Región de un nodo

Figura: Correspondencia entre una región en el plano y un árbol-kd


Range Trees Búsquedas de rango rectangular

3 Range TreesBúsquedas de rango rectangularSubconjuntos canónicosConstrucciónConsultas



Búsquedas de rango rectangular

En la sección anterior describimos los árboles Kd, los cuales tienenun tiempo de consulta O(

√n + k). Cuando el número de puntos

reportados es pequeño, el tiempo de consulta es relativamentealto.

En esta sección describiremos otra estructura de datos parabúsquedas en rangos rectangulares, llamada range tree. Tiene unmejor tiempo de consulta, acotado por O(log n2 + k), pero elprecio a pagar es un incremento en el almacenamiento de O(n)(para los árboles Kd) a O(n log n).




Sea P un conjunto de n puntos en el plano el cual queremosejecutar búsquedas de rango rectangular. Definamos el rango debúsqueda como

[x : x′]× [y : y′]

Nos concentraremos en encontrar primero los puntos cuyacoordenada x estén en [x : x′], y no nos preocuparemos por lacoordenada y después.

Si sólo nos preocupamos por la coordenada x, entonces labúsqueda se reduce a una búsqueda de rango 1-dimensional.Como ya sabemos, para proceder con esta búsqueda basta unabúsqueda binaria.




Nuestro algoritmo de búsqueda procedía de la manera siguiente:Buscamos con x y x′ en el árbol hasta encontrar un nodo vsplit dondela ruta de búsqueda se bifurque.

Desde el hijo izquierdo de vsplit continuamos la búsqueda con x, yen cada nodo v donde la ruta de búsqueda de x siga hacia laizquierda, reportamos todos los puntos en el subárbol izquierdo dev.

De manera similar, continuamos la búsqueda con x′ en el hijoderecho de vsplit, y en cada nodo v donde la ruta de búsqueda de x′

siga a la derecha, reportamos todos los puntos en el subárbolizquierdo de v.

Finalmente, evaluamos las hojas µ y µ′ donde las dos rutasterminan para ver si contienen un punto en el rango. En efectoseleccionamos una colección de O(log n) subárboles que juntoscontienen exactamente los puntos cuya coordenada x cae dentro delrango de la búsqueda.




Figura: Representación gráfica de la búsqueda 1-dimensional en un árbol Kd


Range Trees Subconjuntos canónicos



Range Trees Subconjuntos canónicos

Subconjuntos canónicos

Llamaremos subconjunto canónico de v al subconjunto de puntosguardados en las hojas del del subárbol con raíz v. Podemos decirentonces que el subconjunto canónico de la raíz del árbol es elconjunto P y que el subconjunto canónico de una hoja es el puntoguardado en esa hoja.

Denotamos el subconjunto canónico de v como P(v).

Usando este nuevo concepto podemos decir que el subconjuntode puntos cuya coordenada x cae en un rango de búsqueda puedeser expresado como la unión disjunta de O(log n) subconjuntoscanónicos.


Range Trees Construcción




Construcción

No estamos interesados en todos los puntos de tal subconjuntocanónico P(v), sólo queremos reportar aquellos cuya coordenada ycae dentro del intervalo [y : y′].

Lo anterior nos lleva a definir la siguiente estructura de datos parabúsquedas en rangos rectangulares en un conjunto P de n puntosen el plano:

El árbol principal es un árbol binario balanceado T construidosobre la coordenada x de los puntos en P.Para cualquier nodo interno u hoja v en T , el subconjunto canónicoP(v) es guardado en un árbol binario balanceado Tassoc(v) en lacoordenada y de los puntos. El nodo v guarda un puntero a la raízde Tassoc(v), el cual es llamado la estructura asociada de v.

Esta estructura de datos es llamada range tree. La siguiente figurailustra un range tree.



Construcción

Figura: Un range tree 2-dimensional



Construcción

Aquellas estructuras donde los nodos tienen punteros aestructuras asociadas, son llamadas a menudo estructuras de datosmulti-nivel. El árbol principal es entonces llamado el árbol de primernivel, y las estructuras asociadas son árboles de segundo nivel.

Para la construcción de un range tree puede usarse el siguientealgoritmo recursivo, que recibe como entrada un conjuntoP := {p1, ..., pn} de puntos ordenados en su coordenada x yregresa la raíz de un range tree 2-dimensional T de P.Asumiremos posición general.



Construcción



Construcción

LemmaUn range tree en un conjunto de n puntos en el plano requiereO(n log n) de almacenamiento.



Construcción

Comprobación

Un punto p en P es almacenado sólo en la estructura asociada denodos en la ruta en T hacia la hoja que contiene p. Por lo tanto, paratodos los nodos a una profundidad dada de T , el punto p es guardadoen exactamente una estructura asociada.Dado que los range trees 1-dimensionales usan almacenamiento linealpodemos decir que las estructuras asociadas a todos los nodos decualquier profundidad de T juntos usan O(n) de almacenamiento. Laprofundidad de T es O(log n). De ahí es que la cantidad total dealmacenamiento requerida esta acotada por O(n log n)



Construcción

Figura: Ilustración del almacenamiento requerido por un range tree


Range Trees Consultas




Consultas

El algoritmo de consulta primero selecciona O(log n)subconjuntos canónicos que juntos contienen los puntos cuyacoordenada x cae dentro del rango [x : x′].

De esos puntos reportamos entonces los puntos cuya coordenaday cae en el rango [y : y′].

Dado a que para las dos búsquedas podemos usar el algoritmo debúsqueda en una dimensión, este algoritmo es virtualmente elmismo; la única diferencia es el reemplazo de las llamadas aREPORTSUBTREE por las llamadas a 1DRANGEQUERY.



Consultas



Consultas

LemmaUna consulta con un rectángulo de ejes paralelos en un range treealmacenando n puntos toma tiempo O(log2 n + k), donde k es elnúmero de puntos reportados.



Consultas

Comprobación

En cada nodo v del árbol principal T usamos tiempo constante paradecidir dónde continúa la ruta de búsqueda, y posiblemente llamemosa 1DRANGEQUERY. El tiempo que toma esta llamada recursiva esO(log n + kv), donde kv es el número de puntos reportados en estallamada. Por lo tanto, el tiempo total puede ser expresado por,∑

v

O(log n + kv)



Consultas

TeoremaSea P un conjunto de n puntos en el plano. Un range tree para P usa unalmacenamiento O(n log n) y puede ser construido en tiempoO(n log n). Al hacer una consulta en este range tree se pueden reportarlos puntos en P que caen en un rango de búsqueda rectangular entiempo O(log2 n + k), donde k es el número de puntos reportados.


Higher-Dimensional Range Trees Construcción

4 Higher-Dimensional Range TreesConstrucciónConsultas



Construcción

Sea P un conjunto de puntos en un espacio d-dimensional.Construimos un árbol binario balanceado en la primeracoordenada de los puntos. El subconjunto canónico P(v) de unnodo v en el primer nivel, consiste de los puntos almacenados enlas hojas del subárbol con raíz v. Para cada nodo v construimosuna estructura asociada Tassoc(v); el árbol de segundo nivel Tassoc esun range tree (d− 1)-dimensional para los puntos en P(v),restringidos a su últimas d− 1 coordenadas.



Construcción

El range tree (d− 1)-dimensional es construido recursivamente dela misma forma: es un árbol binario balanceado en la segundacoordenada de los puntos, en el que cada nodo tiene un puntero aun range tree (d− 2)-dimensional de puntos en su subárbol,restringido hasta las últimas (d− 2) coordenadas.

La recurrencia se detiene cuando quedan sólo puntos restringidosa su última coordenada y son guardados en un range tree1-dimensional.



Construcción

Figura: Representación de un range tree d-dimensional


Higher-Dimensional Range Trees Consultas

4 Higher-Dimensional Range TreesConstrucciónConsultas



Consultas

El algoritmo de consulta es muy similar al caso 2-dimensional.Usamos el árbol de primer nivel para localizar O(log n) nodoscuyos subconjuntos canónicos contienen juntos todos los puntoscuyas primeras coordenadas caen dentro del rango correcto. Esossubconjuntos son consultados posteriormente, haciendo unabúsqueda de rango en las estructuras de segundo nivelcorrespondientes.

En cada estructura de segundo nivel, seleccionamos O(log n)subconjuntos canónicos. Esto significa que hay O(log2 n)subconjuntos canónicos en las estructuras de segundo nivel entotal. Juntos, contienen todos los puntos cuya primera y segundacoordenada caen dentro de los rangos correctos.



Consultas

Las estructuras de tercer nivel son consultadas con el rango parala tercera coordenada y así sucesivamente, hasta llegar a losárboles 1-dimensionales. En ellos encontramos los puntos cuyaúltima coordenada cae dentro del rango correcto y los reportamos.

TeoremaSea P un conjunto de n puntos en un espacio d-dimensional, donded ≥ 2. Un range tree para P usa almacenamiento O(n logd−1 n) y puedeser construido en tiempo O(n logd−1 n). Se pueden reportar los puntosen P que caen en una búsqueda de rango rectangular en tiempoO(logd n + k), donde k es el número de puntos reportados.


General Set of Points

5 General Set of Points



Hasta ahora se ha asumido que ningún par de puntos tienencoordenadas x o y iguales, lo cual no es nada realista. Pero esto esrelativamente fácil de remediar.

Si reemplazamos las coordenadas, las cuales son números reales,por elementos del espacio de números compuestos. Los elementos dedicho espacio son pares de reales. El número compuesto de dosreales a y b se denota por (a|b). Definimos entonces un orden totalen el espacio de números compuestos usando un ordenlexicográfico, de tal forma que para dos números compuestos (a|b)y (a′|b′), tenemos

(a|b) < (a′|b′)⇔ a < a′ or (a = a′ and b < b′)



Asumimos un conjunto P de n puntos en el plano. Los puntos sondistintos pero muchos tienen la misma coordenada x o y.

Reemplazamos cada punto p := (px, py) por un nuevo puntop̂ := ((px|py), (py|px)).

De esta forma obtenemos el conjunto P̂ de n puntos. La primeracoordenada de cualesquiera dos puntos en P̂ son distintas, lomismo para la segunda coordenada.



Si suponemos que queremos reportar los puntos de P que caendentro del rango R := [x : x′]× [y : y′]. Para este fin, debemosconsultar el árbol que se construya para P̂. Esto significa quetambién tenemos que transformar el rango. El rangotransformado R̂ es definido como sigue:

R̂ := [(x| −∞) : (x′|+∞)]× [(y| −∞) : (y′|+∞)]



LemmaSea p un punto y R un rango rectangular. Entonces:

p ∈ R⇔ p̂ ∈ R̂



DemostraciónSea R := [x : x′]× [y : y′] y sea p := (px, py). Por definición p cae en R siy sólo si x ≤ px ≤ x′ y y ≤ py ≤ y′. Esto es evidente si y sólo si(x| −∞) ≤ (px|py) ≤ (x′|+∞) y (y| −∞) ≤ (py|px) ≤ (y′|+∞), esto es,si y sólo si p̂ está dentro de R̂.


Fractional Cascading

6 Fractional Cascading



Si retomamos el concepto de range tree, recordamos que el tiempode búsqueda en una de las estructuras Tassoc(v) es una búsquedade rango 1-dimensional la cual toma tiempo O(log n + kv) dondekv es el número de puntos reportados. Por lo tanto el tiempo totalde la búsqueda en el árbol 2-dimensional es O(log2 n + k).

Si pudiésemos buscar en las estructuras asociadas en un tiempoO(1 + kv), podríamos reducir el tiempo total a O(log n + k).

En general no es posible responder a una búsqueda 1-dimensionalen tiempo O(1 + k), con k el número de respuestas.



La ventaja que se tiene es que en una búsqueda d-dimensional seincluyen muchas búsquedas 1-dimensionales con el mismo rango ypodemos usar el resultado de una para acelerar las otras.

Ilustrando, sean S1 y S2 dos conjuntos de objetos, donde cadaobjeto tiene una llave que es un número real. Esos objetos estánguardados en arreglos A1 y A2.

Supongamos que queremos reportar todos los objetos de S1 y S2que caen dentro del rango [y : y′].



Hacemos una búsqueda binaria con y en A1 para encontrar lallave mas pequeña más grande o igual que y. Desde ese puntocaminamos en el arreglo hacia la derecha reportando todos losobjetos, hasta encontrar una llave mayor que y′.

Los objetos de S2 pueden ser reportados de manera similar. Por lotanto el tiempo de consulta sería O(k) mas el tiempo por las dosconsultas binarias, en A1 y A2

Sin embargo, si las llaves de los objetos en S2 son un subconjuntode las llaves de los objetos de S1, podríamos evadir la segundabúsqueda binaria de la siguiente forma:



Si añadimos punteros desde las entradas en A1 a las entradas enA2: si A1[i] guarda un objeto con una llave yi, entonces guardamosun puntero a la entrada en A2 con la llave mas pequeña, mayor oigual a yi. Si no existe tal llave, entonces el puntero de A1[i] es nulo.



Figura: Acelerando la búsqueda añadiendo punteros



Para buscar los puntos en el intervalo [y : y′]

Para reportar los objetos en S1 se procede de la misma forma: unabúsqueda binaria en A1.

Para reportar los objetos de S2, buscamos y en A1 para terminar enA1[i]. Como la llave de esa entrada es la más pequeña en S1 que esmayor o igual que y y como las llaves de S2 son un subconjunto delas llaves en S1, significa que el puntero de A1[i] debe apuntarllave más pequeña con valor mayor o igual que y.



Por lo tanto, podemos seguir este puntero y desde ahí empezar acaminar a la derecha en A2.

De esta forma la búsqueda binaria en A2 es evitada, y reportar losobjetos de S2 sólo toma tiempo O(1 + k), con k el número depuntos reportados



Regresando a los range trees, la observación crucial que debemoshacer es que existen subconjuntos canónicos P(lc(v)) y P(rc(v))ambos subconjuntos de P(v). Por lo que podemos usar la mismaidea para acelerar la búsqueda. La implementación requiere unaspocas observaciones

Sea T un range tree con un conjunto P de n puntos en el plano

Cada subconjunto canónico es almacenado en una estructuraasociada, pero en vez de usar un arbol binario como estructura,usaremos un arreglo A(v)



Cada entrada en un arreglo A(v) guarda dos punteros: uno aA(lc(v)) y otro hacia A(rc(v)).

De manera más precisa, añadimos los siguientes punteros.Supongamos que A(v)[i] guarda un punto p.

Guardamos un puntero de A(v)[i] a la entrada de A(lc(v)) tal que lacoordenada y del punto p′ guardado ahí, sea la más pequeña mayoro igual a py.El puntero hacia A(rc(v)) es definido de la misma forma, apunta ala entrada tal que la coordenada y del punto guardado ahí sea lamás chica mayor o igual que py.



Esta versión modificada del range tree es llamada layered rangetree.



Figura: El árbol principal de un layered range tree: las hojas sólo muestran lascoordenadas x



Figura: Los arreglos asociados con los nodos del árbol principal, con lacoordenada y de los subconjuntos canónicos en orden



Ahora veamos cómo responder a una búsqueda en un rango[x : x′]× [y : y′] en un árbol de este tipo.

Como ya vimos, buscamos con x y x′ en el árbol principal T paradeterminar O(log n) nodos que juntos contienen los puntos cuyascoordenadas x caen dentro del rango [x : x′].



Tales nodos se encuentran de la siguiente manera:Sea vsplit el nodo donde las dos rutas se parten

Los nodos que nos interesan son los que están por debajo de vsplit

En vsplit encontramos la entrada en A(vsplit) cuya coordenada y es lamenor, mayor o igual que y, esto se puede encontrar en tiempoO(log n) con búsqueda binaria



Mientras seguimos buscando en con x y x′ en el árbol principal,vamos tomando registro de la entrada en los arreglos asociadoscuya coordenada y es la menor, mayor o igual a y

Esto puede mantenerse en tiempo constante siguiendo lospunteros guardados en los arreglos

Ahora, sea v uno de los O(log n) nodos que seleccionamos.Debemos reportar los puntos guardados en A(v) cuya coordenaday caiga en el rango [y : y′]

Para esto basta encontrar el punto con la menor coordenada y,mayor o igual a y para después caminar a la derecha del arregloreportando los puntos mientras su coordenada y sea menor oigual que y′



Por lo tanto, podemos reportar los puntos de A(v) cuyacoordenada y esté en el rango [y : y′] en tiempo O(1 + kv), dondekv es el número de puntos reportados en el nodo v

El tiempo total de búsqueda entonces se vuelve O(log n + k)



TeoremaSea P un conjunto de n puntos en un espacio d-dimensional, donded ≥ 2. Un layered range tree para P usa almacenamiento O(n logd−1 n)y puede ser construido en tiempo O(n logd−1 n). Con este árbolpodemos reportar los puntos de P que caen en un rango rectangular entiempo O(logd−1 n + k), donde k es el número de puntos reportados


Documents

Búsqueda de Rango Ortogonal - CINVESTAVertello/gc/sesion14.pdf · Introducción Consultas de Rango Ortogonal Consultas de Rango Ortogonal A primera vista parece ser que las bases