Download Búsqueda de Rango Ortogonal - Cinvestav

Búsqueda de Rango Ortogonal
Pedro Reta
Auraham Camacho
C INVESTAV-Tamaulipas
8 de marzo del 2013
(C INVESTAV)
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
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
2 / 102
Introducción
Consultas de Rango Ortogonal
Consultas de Rango Ortogonal
El material de la clase de hoy está basado en el capítulo 5 del
siguiente libro:
Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark
Overmars. Computational Geometry: Algorithms and Applications.
Springer, 3rd edition (April 16, 2008), ISBN-10: 3540779736.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
3 / 102
Introducción
Consultas de Rango Ortogonal
Consultas de Rango Ortogonal
A primera vista parece ser que las bases de datos tienen poca
relación con geometría.
Sin embargo, muchos tipos de preguntas o queries pueden ser
representados geométricamente.
Para este fin, se puede realizar la siguiente transformación:
registros → puntos
consultas sobre registros → consultas sobre puntos
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
4 / 102
Introducción
Consultas de Rango Ortogonal
Consultas de Rango Ortogonal
Considere una base de datos para el manejo de personal.
Se desea consultar a todos los empleados que:
Nacieron entre 1950 y 1955
Ganen 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 los
puntos en el plano que cumplan los criterios anteriores.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
5 / 102
Introducción
Consultas de Rango Ortogonal
Consultas de Rango Ortogonal
Figura: Interpretando una consulta geométricamente (2D)
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
6 / 102
Introducción
Consultas de Rango Ortogonal
Consultas de Rango Ortogonal
Ahora, considere agregar otro criterio de búsqueda, el número de
hijos por empleado.
Se desea consultar a todos los empleados que:
Nacieron entre 1950 y 1955
Ganen entre $3 000 y $4 000
Tengan 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 los
puntos en el espacio que cumplan los criterios anteriores.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
7 / 102
Introducción
Consultas de Rango Ortogonal
Consultas de Rango Ortogonal
Figura: Interpretando una consulta geométricamente (3D)
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
8 / 102
Introducción
Consultas de Rango Ortogonal
Consultas de Rango Ortogonal
En general, si estamos interesados en responder consultas sobre d
campos de un registro se debe efectuar la siguiente
transformación:
registros → puntos en un espacio d-dimensional
De igual forma, una consulta sobre registros se tranforma a una
consulta sobre puntos que se encuentran dentro de una caja
paralela a los ejes de un espacio d-dimensional.
A este tipo de consultas se les conoce como consultas de rango
rectangular o consultas de rango ortogonal en geometría
computacional.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
9 / 102
Búsqueda de Rango Ortogonal
2
Búsqueda de Rango 1-Dimensional
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Ejemplo
Nodo de bifurcación vsplit
Algoritmo 1DRangeQuery
Kd-Trees
Algoritmo BuildKdTree
Complejidad
Región de un nodo
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
10 / 102
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Búsqueda de Rango 1-Dimensional
Antes de analizar búsquedas en 2 dimensiones o más, veamos el
caso 1-dimensional.
Los datos serán representados como un conjunto P de puntos en
un espacio 1-dimensional, es decir, números reales sobre la recta.
P = {p1 , p2 , ..., pn }
Una consulta reporta los puntos dentro de un rectángulo
1-dimensional, es decir, un intervalo [x : x0 ].
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
11 / 102
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Búsqueda de Rango 1-Dimensional
Es posible resolver el problema de búsqueda 1-dimensional
usando un árbol de búsqueda balanceado T donde:
Los nodos hoja representan los puntos de P
Los nodos internos representan valores de división para guiar la
bú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 valores
menores o iguales a v y que el subárbol a la derecha de v contiene
valores mayores a v.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
12 / 102
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Búsqueda de Rango 1-Dimensional
Figura: Árbol balanceado de búsqueda
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
13 / 102
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Búsqueda de Rango 1-Dimensional
Para reportar todos los puntos en una búsqueda de rango [x : x0 ] se
procede como sigue.
Sean µ y µ0 los nodos hoja en donde termina la búsqueda
Entonces, los puntos en el intervalo [x : x0 ] son aquellas hojas entre
µ y µ0 1 .
1
µ y µ0 pueden ser límites inclusivos o exclusivos
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
14 / 102
Búsqueda de Rango Ortogonal
2
Ejemplo
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Ejemplo
Nodo de bifurcación vsplit
Algoritmo 1DRangeQuery
Kd-Trees
Algoritmo BuildKdTree
Complejidad
Región de un nodo
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
15 / 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).
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
16 / 102
Búsqueda de Rango Ortogonal
Ejemplo
Ejemplo
Figura: Búsqueda de rango 1-dimensional
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
17 / 102
Búsqueda de Rango Ortogonal
Ejemplo
Ejemplo
Por lo tanto, se deben realizar dos tareas:
Encontrar un nodo de bifurcación vsplit que divida el camino de
búsqueda (color verde).
Encontrar los nodos dentro del rango [x : x0 ].
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
18 / 102
Búsqueda de Rango Ortogonal
2
Nodo de bifurcación vsplit
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Ejemplo
Nodo de bifurcación vsplit
Algoritmo 1DRangeQuery
Kd-Trees
Algoritmo BuildKdTree
Complejidad
Región de un nodo
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
19 / 102
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 .
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
20 / 102
Búsqueda de Rango Ortogonal
Nodo de bifurcación vsplit
Nodo de bifurcación vsplit
Require: Un árbol T y dos valores x y x0 donde x ≤ x0 .
Ensure: El nodo v donde las ramas hacia x y x0 se dividen o la hoja donde ambas ramas
terminan.
function F IND S PLIT N ONE(T , x, x0 )
v ← root(T )
while v no es hoja and (x0 ≤ x or x > xv ) do
if x0 ≤ x then
v ← lc(v)
else
v ← lr(v)
return v
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
21 / 102
Búsqueda de Rango Ortogonal
2
Algoritmo 1DRangeQuery
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Ejemplo
Nodo de bifurcación vsplit
Algoritmo 1DRangeQuery
Kd-Trees
Algoritmo BuildKdTree
Complejidad
Región de un nodo
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
22 / 102
Búsqueda de Rango Ortogonal
Algoritmo 1DRangeQuery
Algoritmo 1DRangeQuery
Enseguida, hace falta reportar aquellos puntos que se encuentran
dentro 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.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
23 / 102
Búsqueda de Rango Ortogonal
Algoritmo 1DRangeQuery
Algoritmo 1DRangeQuery
Require: Un árbol T y dos valores x y x0 donde x ≤ x0 .
Ensure: El nodo v donde las ramas hacia x y x0 se dividen o la hoja donde ambas ramas
terminan.
function 1 D R ANGE Q UERY(T , [x : x0 ])
vsplit ← F IND S PLIT N ODE(T , x, x0 ))
if vsplit es hoja then
Verificar si vsplit se debe reportar
else
v ← lc(vsplit )
while v no sea hoja do
if x ≤ xv then
ReportSubtree(rc(v))
v ← lc(v)
else
v ← rc(v)
Verificar si vsplit se debe reportar
Similarmente, recorrer el camnio hacia x0
Reportar los puntos en los subárboles izquierdos
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
24 / 102
Búsqueda de Rango Ortogonal
Algoritmo 1DRangeQuery
Algoritmo 1DRangeQuery
v
(C INVESTAV)
x
≤
xv
Búsqueda de Rango Ortogonal
8 de marzo del 2013
25 / 102
Búsqueda de Rango Ortogonal
Algoritmo 1DRangeQuery
Algoritmo 1DRangeQuery
(C INVESTAV)
v
x
≤
xv
23
18
≤
23
Búsqueda de Rango Ortogonal
8 de marzo del 2013
26 / 102
Búsqueda de Rango Ortogonal
Algoritmo 1DRangeQuery
Algoritmo 1DRangeQuery
(C INVESTAV)
v
x
≤
xv
23
10
18
18
≤
23
10
Búsqueda de Rango Ortogonal
8 de marzo del 2013
27 / 102
Búsqueda de Rango Ortogonal
Algoritmo 1DRangeQuery
Algoritmo 1DRangeQuery
(C INVESTAV)
v
x
≤
xv
23
10
19
18
18
18
≤
≤
23
10
19
Búsqueda de Rango Ortogonal
8 de marzo del 2013
28 / 102
Búsqueda de Rango Ortogonal
Algoritmo 1DRangeQuery
Algoritmo 1DRangeQuery
(C INVESTAV)
v
x
≤
xv
23
10
19
23
18
18
18
18
≤
≤
≤
23
10
19
23
Búsqueda de Rango Ortogonal
8 de marzo del 2013
29 / 102
Búsqueda de Rango Ortogonal
2
Kd-Trees
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Ejemplo
Nodo de bifurcación vsplit
Algoritmo 1DRangeQuery
Kd-Trees
Algoritmo BuildKdTree
Complejidad
Región de un nodo
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
30 / 102
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 los
puntos están en posición general.
Una consulta de rango rectangular 2-dimensional sobre P reporta
aquellos puntos dentro del rectángulo formado por
[x : x0 ] × [y : y0 ].
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
31 / 102
Búsqueda de Rango Ortogonal
Kd-Trees
Kd-Trees
Un punto p = (px , py ) se encuentra dentro de [x : x0 ] × [y : y0 ] si y
sólo si:
px ∈ [x : x0 ]
(C INVESTAV)
y
py ∈ [y : y0 ]
Búsqueda de Rango Ortogonal
8 de marzo del 2013
32 / 102
Búsqueda de Rango Ortogonal
Kd-Trees
Kd-Trees
En el caso 1-dimensional el árbol binario de búsqueda se crea a
partir de un solo valor, la coordenada x.
En el caso 2-dimensional este árbol se debe crear considerando
dos coordenadas.
Una forma de crear el árbol consiste en dividir el plano en
subconjuntos (mitades) sucesivamente. El procedimiento es el
siguiente.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
33 / 102
Búsqueda de Rango Ortogonal
Kd-Trees
Kd-Trees
Se divide el conjunto P en dos subconjuntos de aproximadamente
el mismo tamaño con una línea l, la cual se almacena en la raíz de
T.
Se obtienen dos subconjuntos:
Pleft contiene aquellos puntos a la izquierda o sobre l
Pright contiene aquellos puntos a la derecha de l
Enseguida, se divide de nuevo los conjuntos anteriores, pero
ahora con una línea horizontal.
A medida que se dividen los subconjuntos, aumenta el nivel de
profundidad el cual llamaremos depth. Veamos un ejemplo.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
34 / 102
Búsqueda de Rango Ortogonal
Kd-Trees
Kd-Trees
depth = 0
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
35 / 102
Búsqueda de Rango Ortogonal
Kd-Trees
Kd-Trees
depth = 1
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
36 / 102
Búsqueda de Rango Ortogonal
Kd-Trees
Kd-Trees
depth = 2
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
37 / 102
Búsqueda de Rango Ortogonal
Kd-Trees
Kd-Trees
depth = 3
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
38 / 102
Búsqueda de Rango Ortogonal
Kd-Trees
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 par
Se divide con una línea horizontal si la profundidad es impar
Al reorganizar los nodos se obtiene el siguiente árbol.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
39 / 102
Búsqueda de Rango Ortogonal
Kd-Trees
Kd-Trees
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
40 / 102
Búsqueda de Rango Ortogonal
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 y
un nivel de profundidad o recursión.
El nivel de profundidad será de utilidad para determinar si se
debe dividir a P con una línea horizontal o vertical.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
41 / 102
Búsqueda de Rango Ortogonal
2
Algoritmo BuildKdTree
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Ejemplo
Nodo de bifurcación vsplit
Algoritmo 1DRangeQuery
Kd-Trees
Algoritmo BuildKdTree
Complejidad
Región de un nodo
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
42 / 102
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.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
43 / 102
Búsqueda de Rango Ortogonal
Algoritmo BuildKdTree
Algoritmo BuildKdTree
Require: Un conjunto de puntos P y una profundidad depth
Ensure: La raíz de un árbol-kd almacenando P
function B UILD K D T REE(P, depth)
if P contiene sólo un punto then
return una hoja con este punto
else
if depth es par then
Dividir P en dos subconjuntos con una línea vertical l
Sea P1 el conjunto de puntos a la izquierda o en l
Sea P2 el conjunto de puntos a la derecha de l
else
Dividir P en dos subconjuntos con una línea horizontal l
Sea P1 el conjunto de puntos abajo o en l
Sea P2 el conjunto de puntos arriba de l
vleft ← B UILD K D T REE(P1 , depth + 1)
vright ← B UILD K D T REE(P2 , depth + 1)
Crear un nodo v que almacene l
Colocar vleft a la izquierda de v
Colocar vright a la derecha de v
return v
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
44 / 102
Búsqueda de Rango Ortogonal
2
Complejidad
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Ejemplo
Nodo de bifurcación vsplit
Algoritmo 1DRangeQuery
Kd-Trees
Algoritmo BuildKdTree
Complejidad
Región de un nodo
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
45 / 102
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 de
la mediana. Si P se encuentra ordenado el proceso de encontrar el
punto de división será más simple. Esto tomará un tiempo
O(n log(n)).
Unión de resultados consiste en agregar los subárboles vleft y
vright a la raíz v. Esto se puede realizar en tiempo O(n).
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
46 / 102
Búsqueda de Rango Ortogonal
Complejidad
Complejidad
Por lo tanto, la complejidad del algoritmo se resume a la siguiente
relación de recurrencia:
(
O(1)
if n = 1
T(n) =
n
O(n) + 2T(d 2 e) if n > 1.
Siendo esto igual a O(n log(n))
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
47 / 102
Búsqueda de Rango Ortogonal
2
Región de un nodo
Búsqueda de Rango Ortogonal
Búsqueda de Rango 1-Dimensional
Ejemplo
Nodo de bifurcación vsplit
Algoritmo 1DRangeQuery
Kd-Trees
Algoritmo BuildKdTree
Complejidad
Región de un nodo
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
48 / 102
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 cual
puede ser abierto en uno o más lados.
Denotamos esta región como region(v).
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
49 / 102
Búsqueda de Rango Ortogonal
Región de un nodo
Región de un nodo
Figura: Correspondencia entre una región en el plano y un árbol-kd
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
50 / 102
Range Trees
3
Búsquedas de rango rectangular
Range Trees
Búsquedas de rango rectangular
Subconjuntos canónicos
Construcción
Consultas
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
51 / 102
Range Trees
Búsquedas de rango rectangular
Búsquedas de rango rectangular
En la sección anterior describimos
los árboles Kd, los cuales tienen
√
un tiempo de consulta O( n + k). Cuando el número de puntos
reportados es pequeño, el tiempo de consulta es relativamente
alto.
En esta sección describiremos otra estructura de datos para
búsquedas en rangos rectangulares, llamada range tree. Tiene un
mejor tiempo de consulta, acotado por O(log n2 + k), pero el
precio a pagar es un incremento en el almacenamiento de O(n)
(para los árboles Kd) a O(n log n).
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
52 / 102
Range Trees
Búsquedas de rango rectangular
Búsquedas de rango rectangular
Sea P un conjunto de n puntos en el plano el cual queremos
ejecutar búsquedas de rango rectangular. Definamos el rango de
búsqueda como
[x : x0 ] × [y : y0 ]
Nos concentraremos en encontrar primero los puntos cuya
coordenada x estén en [x : x0 ], y no nos preocuparemos por la
coordenada y después.
Si sólo nos preocupamos por la coordenada x, entonces la
búsqueda se reduce a una búsqueda de rango 1-dimensional.
Como ya sabemos, para proceder con esta búsqueda basta una
búsqueda binaria.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
53 / 102
Range Trees
Búsquedas de rango rectangular
Búsquedas de rango rectangular
Nuestro algoritmo de búsqueda procedía de la manera siguiente:
Buscamos con x y x0 en el árbol hasta encontrar un nodo vsplit donde
la ruta de búsqueda se bifurque.
Desde el hijo izquierdo de vsplit continuamos la búsqueda con x, y
en cada nodo v donde la ruta de búsqueda de x siga hacia la
izquierda, reportamos todos los puntos en el subárbol izquierdo de
v.
De manera similar, continuamos la búsqueda con x0 en el hijo
derecho de vsplit , y en cada nodo v donde la ruta de búsqueda de x0
siga a la derecha, reportamos todos los puntos en el subárbol
izquierdo de v.
Finalmente, evaluamos las hojas µ y µ0 donde las dos rutas
terminan para ver si contienen un punto en el rango. En efecto
seleccionamos una colección de O(log n) subárboles que juntos
contienen exactamente los puntos cuya coordenada x cae dentro del
rango de la búsqueda.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
54 / 102
Range Trees
Búsquedas de rango rectangular
Búsquedas de rango rectangular
Figura: Representación gráfica de la búsqueda 1-dimensional en un árbol Kd
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
55 / 102
Range Trees
3
Subconjuntos canónicos
Range Trees
Búsquedas de rango rectangular
Subconjuntos canónicos
Construcción
Consultas
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
56 / 102
Range Trees
Subconjuntos canónicos
Subconjuntos canónicos
Llamaremos subconjunto canónico de v al subconjunto de puntos
guardados en las hojas del del subárbol con raíz v. Podemos decir
entonces que el subconjunto canónico de la raíz del árbol es el
conjunto P y que el subconjunto canónico de una hoja es el punto
guardado en esa hoja.
Denotamos el subconjunto canónico de v como P(v).
Usando este nuevo concepto podemos decir que el subconjunto
de puntos cuya coordenada x cae en un rango de búsqueda puede
ser expresado como la unión disjunta de O(log n) subconjuntos
canónicos.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
57 / 102
Range Trees
3
Construcción
Range Trees
Búsquedas de rango rectangular
Subconjuntos canónicos
Construcción
Consultas
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
58 / 102
Range Trees
Construcción
Construcción
No estamos interesados en todos los puntos de tal subconjunto
canónico P(v), sólo queremos reportar aquellos cuya coordenada y
cae dentro del intervalo [y : y0 ].
Lo anterior nos lleva a definir la siguiente estructura de datos para
búsquedas en rangos rectangulares en un conjunto P de n puntos
en el plano:
El árbol principal es un árbol binario balanceado T construido
sobre la coordenada x de los puntos en P.
Para cualquier nodo interno u hoja v en T , el subconjunto canónico
P(v) es guardado en un árbol binario balanceado Tassoc (v) en la
coordenada y de los puntos. El nodo v guarda un puntero a la raíz
de Tassoc (v), el cual es llamado la estructura asociada de v.
Esta estructura de datos es llamada range tree. La siguiente figura
ilustra un range tree.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
59 / 102
Range Trees
Construcción
Construcción
Figura: Un range tree 2-dimensional
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
60 / 102
Range Trees
Construcción
Construcción
Aquellas estructuras donde los nodos tienen punteros a
estructuras asociadas, son llamadas a menudo estructuras de datos
multi-nivel. El árbol principal es entonces llamado el árbol de primer
nivel, y las estructuras asociadas son árboles de segundo nivel.
Para la construcción de un range tree puede usarse el siguiente
algoritmo recursivo, que recibe como entrada un conjunto
P := {p1 , ..., pn } de puntos ordenados en su coordenada x y
regresa la raíz de un range tree 2-dimensional T de P.
Asumiremos posición general.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
61 / 102
Range Trees
Construcción
Construcción
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
62 / 102
Range Trees
Construcción
Construcción
Lemma
Un range tree en un conjunto de n puntos en el plano requiere
O(n log n) de almacenamiento.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
63 / 102
Range Trees
Construcción
Construcción
Comprobación
Un punto p en P es almacenado sólo en la estructura asociada de
nodos en la ruta en T hacia la hoja que contiene p. Por lo tanto, para
todos los nodos a una profundidad dada de T , el punto p es guardado
en exactamente una estructura asociada.
Dado que los range trees 1-dimensionales usan almacenamiento lineal
podemos decir que las estructuras asociadas a todos los nodos de
cualquier profundidad de T juntos usan O(n) de almacenamiento. La
profundidad de T es O(log n). De ahí es que la cantidad total de
almacenamiento requerida esta acotada por O(n log n)
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
64 / 102
Range Trees
Construcción
Construcción
Figura: Ilustración del almacenamiento requerido por un range tree
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
65 / 102
Range Trees
3
Consultas
Range Trees
Búsquedas de rango rectangular
Subconjuntos canónicos
Construcción
Consultas
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
66 / 102
Range Trees
Consultas
Consultas
El algoritmo de consulta primero selecciona O(log n)
subconjuntos canónicos que juntos contienen los puntos cuya
coordenada x cae dentro del rango [x : x0 ].
De esos puntos reportamos entonces los puntos cuya coordenada
y cae en el rango [y : y0 ].
Dado a que para las dos búsquedas podemos usar el algoritmo de
búsqueda en una dimensión, este algoritmo es virtualmente el
mismo; la única diferencia es el reemplazo de las llamadas a
REPORTSUBTREE por las llamadas a 1DRANGEQUERY.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
67 / 102
Range Trees
Consultas
Consultas
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
68 / 102
Range Trees
Consultas
Consultas
Lemma
Una consulta con un rectángulo de ejes paralelos en un range tree
almacenando n puntos toma tiempo O(log2 n + k), donde k es el
número de puntos reportados.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
69 / 102
Range Trees
Consultas
Consultas
Comprobación
En cada nodo v del árbol principal T usamos tiempo constante para
decidir dónde continúa la ruta de búsqueda, y posiblemente llamemos
a 1DRANGEQUERY. El tiempo que toma esta llamada recursiva es
O(log n + kv ), donde kv es el número de puntos reportados en esta
llamada. Por lo tanto, el tiempo total puede ser expresado por,
X
O(log n + kv )
v
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
70 / 102
Range Trees
Consultas
Consultas
Teorema
Sea P un conjunto de n puntos en el plano. Un range tree para P usa un
almacenamiento O(n log n) y puede ser construido en tiempo
O(n log n). Al hacer una consulta en este range tree se pueden reportar
los puntos en P que caen en un rango de búsqueda rectangular en
tiempo O(log2 n + k), donde k es el número de puntos reportados.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
71 / 102
Higher-Dimensional Range Trees
4
Construcción
Higher-Dimensional Range Trees
Construcción
Consultas
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
72 / 102
Higher-Dimensional Range Trees
Construcción
Construcción
Sea P un conjunto de puntos en un espacio d-dimensional.
Construimos un árbol binario balanceado en la primera
coordenada de los puntos. El subconjunto canónico P(v) de un
nodo v en el primer nivel, consiste de los puntos almacenados en
las hojas del subárbol con raíz v. Para cada nodo v construimos
una estructura asociada Tassoc (v); el árbol de segundo nivel Tassoc es
un range tree (d − 1)-dimensional para los puntos en P(v),
restringidos a su últimas d − 1 coordenadas.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
73 / 102
Higher-Dimensional Range Trees
Construcción
Construcción
El range tree (d − 1)-dimensional es construido recursivamente de
la misma forma: es un árbol binario balanceado en la segunda
coordenada de los puntos, en el que cada nodo tiene un puntero a
un 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 restringidos
a su última coordenada y son guardados en un range tree
1-dimensional.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
74 / 102
Higher-Dimensional Range Trees
Construcción
Construcción
Figura: Representación de un range tree d-dimensional
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
75 / 102
Higher-Dimensional Range Trees
4
Consultas
Higher-Dimensional Range Trees
Construcción
Consultas
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
76 / 102
Higher-Dimensional Range Trees
Consultas
Consultas
El algoritmo de consulta es muy similar al caso 2-dimensional.
Usamos el árbol de primer nivel para localizar O(log n) nodos
cuyos subconjuntos canónicos contienen juntos todos los puntos
cuyas primeras coordenadas caen dentro del rango correcto. Esos
subconjuntos son consultados posteriormente, haciendo una
búsqueda de rango en las estructuras de segundo nivel
correspondientes.
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 en
total. Juntos, contienen todos los puntos cuya primera y segunda
coordenada caen dentro de los rangos correctos.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
77 / 102
Higher-Dimensional Range Trees
Consultas
Consultas
Las estructuras de tercer nivel son consultadas con el rango para
la 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.
Teorema
Sea P un conjunto de n puntos en un espacio d-dimensional, donde
d ≥ 2. Un range tree para P usa almacenamiento O(n logd−1 n) y puede
ser construido en tiempo O(n logd−1 n). Se pueden reportar los puntos
en P que caen en una búsqueda de rango rectangular en tiempo
O(logd n + k), donde k es el número de puntos reportados.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
78 / 102
General Set of Points
5
General Set of Points
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
79 / 102
General Set of Points
Hasta ahora se ha asumido que ningún par de puntos tienen
coordenadas x o y iguales, lo cual no es nada realista. Pero esto es
relativamente fácil de remediar.
Si reemplazamos las coordenadas, las cuales son números reales,
por elementos del espacio de números compuestos. Los elementos de
dicho espacio son pares de reales. El número compuesto de dos
reales a y b se denota por (a|b). Definimos entonces un orden total
en el espacio de números compuestos usando un orden
lexicográfico, de tal forma que para dos números compuestos (a|b)
y (a0 |b0 ), tenemos
(a|b) < (a0 |b0 ) ⇔ a < a0 or (a = a0 and b < b0 )
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
80 / 102
General Set of Points
Asumimos un conjunto P de n puntos en el plano. Los puntos son
distintos pero muchos tienen la misma coordenada x o y.
Reemplazamos cada punto p := (px , py ) por un nuevo punto
p̂ := ((px |py ), (py |px )).
De esta forma obtenemos el conjunto P̂ de n puntos. La primera
coordenada de cualesquiera dos puntos en P̂ son distintas, lo
mismo para la segunda coordenada.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
81 / 102
General Set of Points
Si suponemos que queremos reportar los puntos de P que caen
dentro del rango R := [x : x0 ] × [y : y0 ]. Para este fin, debemos
consultar el árbol que se construya para P̂. Esto significa que
también tenemos que transformar el rango. El rango
transformado R̂ es definido como sigue:
R̂ := [(x| − ∞) : (x0 | + ∞)] × [(y| − ∞) : (y0 | + ∞)]
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
82 / 102
General Set of Points
Lemma
Sea p un punto y R un rango rectangular. Entonces:
p ∈ R ⇔ p̂ ∈ R̂
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
83 / 102
General Set of Points
Demostración
Sea R := [x : x0 ] × [y : y0 ] y sea p := (px , py ). Por definición p cae en R si
y sólo si x ≤ px ≤ x0 y y ≤ py ≤ y0 . Esto es evidente si y sólo si
(x| − ∞) ≤ (px |py ) ≤ (x0 | + ∞) y (y| − ∞) ≤ (py |px ) ≤ (y0 | + ∞), esto es,
si y sólo si p̂ está dentro de R̂.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
84 / 102
Fractional Cascading
6
Fractional Cascading
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
85 / 102
Fractional Cascading
Si retomamos el concepto de range tree, recordamos que el tiempo
de búsqueda en una de las estructuras Tassoc (v) es una búsqueda
de rango 1-dimensional la cual toma tiempo O(log n + kv ) donde
kv es el número de puntos reportados. Por lo tanto el tiempo total
de la búsqueda en el árbol 2-dimensional es O(log2 n + k).
Si pudiésemos buscar en las estructuras asociadas en un tiempo
O(1 + kv ), podríamos reducir el tiempo total a O(log n + k).
En general no es posible responder a una búsqueda 1-dimensional
en tiempo O(1 + k), con k el número de respuestas.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
86 / 102
Fractional Cascading
La ventaja que se tiene es que en una búsqueda d-dimensional se
incluyen muchas búsquedas 1-dimensionales con el mismo rango y
podemos usar el resultado de una para acelerar las otras.
Ilustrando, sean S1 y S2 dos conjuntos de objetos, donde cada
objeto tiene una llave que es un número real. Esos objetos están
guardados en arreglos A1 y A2 .
Supongamos que queremos reportar todos los objetos de S1 y S2
que caen dentro del rango [y : y0 ].
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
87 / 102
Fractional Cascading
Hacemos una búsqueda binaria con y en A1 para encontrar la
llave mas pequeña más grande o igual que y. Desde ese punto
caminamos en el arreglo hacia la derecha reportando todos los
objetos, hasta encontrar una llave mayor que y0 .
Los objetos de S2 pueden ser reportados de manera similar. Por lo
tanto el tiempo de consulta sería O(k) mas el tiempo por las dos
consultas binarias, en A1 y A2
Sin embargo, si las llaves de los objetos en S2 son un subconjunto
de las llaves de los objetos de S1 , podríamos evadir la segunda
búsqueda binaria de la siguiente forma:
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
88 / 102
Fractional Cascading
Si añadimos punteros desde las entradas en A1 a las entradas en
A2 : si A1 [i] guarda un objeto con una llave yi , entonces guardamos
un puntero a la entrada en A2 con la llave mas pequeña, mayor o
igual a yi . Si no existe tal llave, entonces el puntero de A1 [i] es nulo.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
89 / 102
Fractional Cascading
Figura: Acelerando la búsqueda añadiendo punteros
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
90 / 102
Fractional Cascading
Para buscar los puntos en el intervalo [y : y0 ]
Para reportar los objetos en S1 se procede de la misma forma: una
búsqueda binaria en A1 .
Para reportar los objetos de S2 , buscamos y en A1 para terminar en
A1 [i]. Como la llave de esa entrada es la más pequeña en S1 que es
mayor o igual que y y como las llaves de S2 son un subconjunto de
las llaves en S1 , significa que el puntero de A1 [i] debe apuntar
llave más pequeña con valor mayor o igual que y.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
91 / 102
Fractional Cascading
Por lo tanto, podemos seguir este puntero y desde ahí empezar a
caminar a la derecha en A2 .
De esta forma la búsqueda binaria en A2 es evitada, y reportar los
objetos de S2 sólo toma tiempo O(1 + k), con k el número de
puntos reportados
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
92 / 102
Fractional Cascading
Regresando a los range trees, la observación crucial que debemos
hacer es que existen subconjuntos canónicos P(lc(v)) y P(rc(v))
ambos subconjuntos de P(v). Por lo que podemos usar la misma
idea para acelerar la búsqueda. La implementación requiere unas
pocas observaciones
Sea T un range tree con un conjunto P de n puntos en el plano
Cada subconjunto canónico es almacenado en una estructura
asociada, pero en vez de usar un arbol binario como estructura,
usaremos un arreglo A(v)
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
93 / 102
Fractional Cascading
Cada entrada en un arreglo A(v) guarda dos punteros: uno a
A(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 la
coordenada y del punto p0 guardado ahí, sea la más pequeña mayor
o igual a py .
El puntero hacia A(rc(v)) es definido de la misma forma, apunta a
la entrada tal que la coordenada y del punto guardado ahí sea la
más chica mayor o igual que py .
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
94 / 102
Fractional Cascading
Esta versión modificada del range tree es llamada layered range
tree.
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
95 / 102
Fractional Cascading
Figura: El árbol principal de un layered range tree: las hojas sólo muestran las
coordenadas x
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
96 / 102
Fractional Cascading
Figura: Los arreglos asociados con los nodos del árbol principal, con la
coordenada y de los subconjuntos canónicos en orden
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
97 / 102
Fractional Cascading
Ahora veamos cómo responder a una búsqueda en un rango
[x : x0 ] × [y : y0 ] en un árbol de este tipo.
Como ya vimos, buscamos con x y x0 en el árbol principal T para
determinar O(log n) nodos que juntos contienen los puntos cuyas
coordenadas x caen dentro del rango [x : x0 ].
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
98 / 102
Fractional Cascading
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 la
menor, mayor o igual que y, esto se puede encontrar en tiempo
O(log n) con búsqueda binaria
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
99 / 102
Fractional Cascading
Mientras seguimos buscando en con x y x0 en el árbol principal,
vamos tomando registro de la entrada en los arreglos asociados
cuya coordenada y es la menor, mayor o igual a y
Esto puede mantenerse en tiempo constante siguiendo los
punteros 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 coordenada
y caiga en el rango [y : y0 ]
Para esto basta encontrar el punto con la menor coordenada y,
mayor o igual a y para después caminar a la derecha del arreglo
reportando los puntos mientras su coordenada y sea menor o
igual que y0
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
100 / 102
Fractional Cascading
Por lo tanto, podemos reportar los puntos de A(v) cuya
coordenada y esté en el rango [y : y0 ] en tiempo O(1 + kv ), donde
kv es el número de puntos reportados en el nodo v
El tiempo total de búsqueda entonces se vuelve O(log n + k)
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
101 / 102
Fractional Cascading
Teorema
Sea P un conjunto de n puntos en un espacio d-dimensional, donde
d ≥ 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 árbol
podemos reportar los puntos de P que caen en un rango rectangular en
tiempo O(logd−1 n + k), donde k es el número de puntos reportados
(C INVESTAV)
Búsqueda de Rango Ortogonal
8 de marzo del 2013
102 / 102