árbol kd

Árbol de búsqueda multidimensional de puntos en un espacio de dimensión k

En informática , un árbol k -d (abreviatura de árbol k-dimensional ) es una estructura de datos que divide el espacio en partes para organizar puntos en un espacio k -dimensional . K-dimensional es aquel que concierne exactamente a k ejes ortogonales o a un espacio de cualquier número de dimensiones . ^{[1] Los árboles} k -d son una estructura de datos útil para varias aplicaciones, como:

• Búsquedas que involucran una clave de búsqueda multidimensional (por ejemplo, búsquedas de rango y búsquedas de vecino más cercano ) y
• Creando nubes de puntos .

Los árboles k -d son un caso especial de árboles de partición de espacio binario .

Descripción

El árbol k -d es un árbol binario en el que cada nodo es un punto de dimensión k . ^[2] Se puede pensar que cada nodo que no es una hoja genera implícitamente un hiperplano divisor que divide el espacio en dos partes, conocidas como semiespacios . Los puntos a la izquierda de este hiperplano están representados por el subárbol izquierdo de ese nodo y los puntos a la derecha del hiperplano están representados por el subárbol derecho. La dirección del hiperplano se elige de la siguiente manera: cada nodo del árbol está asociado con una de las dimensiones k , con el hiperplano perpendicular al eje de esa dimensión. Entonces, por ejemplo, si para una división particular se elige el eje "x", todos los puntos en el subárbol con un valor "x" menor que el nodo aparecerán en el subárbol izquierdo y todos los puntos con un valor "x" mayor estarán en el subárbol derecho. En tal caso, el hiperplano estaría determinado por el valor x del punto, y su normal sería el eje x unitario. ^[3]

Ejemplo de un árbol kd tridimensional

Operaciones ena-d árboles

Construcción

Dado que existen muchas formas posibles de elegir planos de división alineados con los ejes, existen muchas formas diferentes de construir árboles k -d. El método canónico de construcción de árboles k -d tiene las siguientes restricciones: ^[4]

• A medida que uno se desplaza hacia abajo en el árbol, va recorriendo los ejes utilizados para seleccionar los planos de división. (Por ejemplo, en un árbol tridimensional, la raíz tendría un plano alineado con x , los hijos de la raíz tendrían ambos planos alineados con y , los nietos de la raíz tendrían todos planos alineados con z , los bisnietos de la raíz tendrían todos planos alineados con x , los tataranietos de la raíz tendrían todos planos alineados con y , y así sucesivamente).
• Los puntos se insertan seleccionando la mediana de los puntos que se colocan en el subárbol , con respecto a sus coordenadas en el eje que se utiliza para crear el plano de división. (Tenga en cuenta la suposición de que introducimos todo el conjunto de n puntos en el algoritmo por adelantado).

Este método conduce a un árbol k -d equilibrado , en el que cada nodo de hoja se encuentra aproximadamente a la misma distancia de la raíz. Sin embargo, los árboles equilibrados no son necesariamente óptimos para todas las aplicaciones.

Tenga en cuenta que no es necesario seleccionar el punto medio. En el caso de que no se seleccionen puntos medios, no hay garantía de que el árbol esté equilibrado. Para evitar codificar un algoritmo complejo de búsqueda de la mediana ^{[5] [6]} o utilizar una ordenación como heapsort o mergesort para ordenar los n puntos, una práctica popular es ordenar una cantidad fija de puntos seleccionados aleatoriamente y utilizar la mediana de esos puntos para que sirva como plano de división. En la práctica, esta técnica a menudo da como resultado árboles bien equilibrados. ${\displaystyle O(n)}$ ${\displaystyle O(n\log(n))}$

Dada una lista de n puntos, el siguiente algoritmo utiliza una ordenación que busca la mediana para construir un árbol k -d equilibrado que contiene esos puntos.

función kdtree ( lista de puntos pointList, int profundidad){ // Seleccione el eje en función de la profundidad para que el eje recorra todos los valores válidos  var  int axis := depth mod k; // Ordena la lista de puntos y elige la mediana como elemento pivote  select mediana por eje from pointList; // Crea un nodo y construye un subárbol nodo.ubicación := mediana; node.leftChild := kdtree(puntos en pointList antes de la mediana, profundidad+1); node.rightChild := kdtree(puntos en pointList después de la mediana, profundidad+1); retorna nodo;}

Es común que los puntos "después" de la mediana incluyan solo aquellos que son estrictamente mayores que la mediana en la dimensión actual. Para los puntos que se encuentran en la mediana en la dimensión actual, es posible definir una función que los compare en todas las dimensiones. En algunos casos, es aceptable dejar que los puntos iguales a la mediana se encuentren en un lado de la mediana, por ejemplo, dividiendo los puntos en un subconjunto "menor que" y un subconjunto "mayor o igual que".

Este algoritmo crea la invariante de que, para cualquier nodo, todos los nodos del subárbol izquierdo están en un lado de un plano de división y todos los nodos del subárbol derecho están en el otro lado. Los puntos que se encuentran en el plano de división pueden aparecer en cualquiera de los lados. El plano de división de un nodo pasa por el punto asociado con ese nodo (al que se hace referencia en el código como node.location ).

Los algoritmos alternativos para construir un árbol k -d equilibrado preordenan los datos antes de construir el árbol. Luego, mantienen el orden de la preordenación durante la construcción del árbol y, por lo tanto, eliminan el costoso paso de encontrar la mediana en cada nivel de subdivisión. Dos de estos algoritmos construyen un árbol k -d equilibrado para ordenar triángulos con el fin de mejorar el tiempo de ejecución del trazado de rayos para gráficos de computadora tridimensionales . Estos algoritmos preordenan n triángulos antes de construir el árbol k -d y luego construyen el árbol a tiempo en el mejor de los casos. ^{[7] [8]} Un algoritmo que construye un árbol k -d equilibrado para ordenar puntos tiene una complejidad en el peor de los casos de . ^{[9] [10]} Este algoritmo preordena n puntos en cada una de las k dimensiones utilizando una ordenación como Heapsort o Mergesort antes de construir el árbol. Luego mantiene el orden de estas k preordenaciones durante la construcción del árbol y, por lo tanto, evita encontrar la mediana en cada nivel de subdivisión. ${\displaystyle O(n\log n)}$ ${\displaystyle O(kn\log(n))}$ ${\displaystyle O(n\log(n))}$

Añadiendo elementos

Se agrega un nuevo punto a un árbol k -d de la misma manera que se agrega un elemento a cualquier otro árbol de búsqueda . Primero, recorra el árbol, comenzando desde la raíz y moviéndose hacia el hijo izquierdo o derecho dependiendo de si el punto que se insertará está en el lado "izquierdo" o "derecho" del plano de división. Una vez que llegue al nodo bajo el cual se debe ubicar el hijo, agregue el nuevo punto como el hijo izquierdo o derecho del nodo hoja, nuevamente dependiendo de qué lado del plano de división del nodo contenga el nuevo nodo.

Agregar puntos de esta manera puede hacer que el árbol se desequilibre, lo que lleva a una disminución del rendimiento del árbol. La tasa de degradación del rendimiento del árbol depende de la distribución espacial de los puntos que se agregan y de la cantidad de puntos agregados en relación con el tamaño del árbol. Si un árbol se desequilibra demasiado, es posible que sea necesario volver a equilibrarlo para restaurar el rendimiento de las consultas que dependen del equilibrio del árbol, como la búsqueda del vecino más cercano.

Eliminación de elementos

Para eliminar un punto de un árbol k -d existente sin romper el invariante, la forma más fácil es formar el conjunto de todos los nodos y hojas a partir de los hijos del nodo de destino y recrear esa parte del árbol. ^[11]

Otro enfoque es encontrar un reemplazo para el punto eliminado. ^[12] Primero, encuentre el nodo que contiene el punto que se eliminará. Para el caso base, donde R es un nodo hoja, no se requiere reemplazo. Para el caso general, encuentre un punto de reemplazo, digamos , del subárbol con raíz en . Reemplace el punto almacenado en con . Luego, elimine recursivamente . ${\displaystyle R}$ ${\displaystyle p}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle p}$ ${\displaystyle p}$

Para encontrar un punto de reemplazo, si discrimina por (por ejemplo) y tiene un hijo derecho, encuentre el punto con el valor mínimo del subárbol con raíz en el hijo derecho. De lo contrario, encuentre el punto con el valor máximo del subárbol con raíz en el hijo izquierdo. ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle x}$

Equilibrio

Equilibrar un árbol k -d requiere cuidado porque los árboles k -d se ordenan en múltiples dimensiones, por lo que no se puede utilizar la técnica de rotación de árboles para equilibrarlos ya que esto puede romper el invariante.

Existen varias variantes de árboles k -d balanceados, entre ellas , el árbol k -d dividido, el pseudoárbol k -d, el árbol KDB , el árbol hB y el árbol Bkd . Muchas de estas variantes son árboles kd adaptativos .

Búsqueda de vecino más cercano

Ejemplo de búsqueda del vecino más próximo en un árbol 2D. Aquí, el árbol ya está construido, cada nodo corresponde a un rectángulo, cada rectángulo está dividido en dos subrectángulos iguales y las hojas corresponden a rectángulos que contienen un único punto.

El algoritmo de búsqueda del vecino más próximo (NN) tiene como objetivo encontrar el punto en el árbol que se encuentra más próximo a un punto de entrada determinado. Esta búsqueda se puede realizar de manera eficiente utilizando las propiedades del árbol para eliminar rápidamente grandes porciones del espacio de búsqueda.

La búsqueda de un vecino más cercano en un árbol k -d se realiza de la siguiente manera:

1. Comenzando con el nodo raíz, el algoritmo se mueve hacia abajo en el árbol recursivamente, de la misma manera que lo haría si se insertara el punto de búsqueda (es decir, va hacia la izquierda o la derecha dependiendo de si el punto es menor o mayor que el nodo actual en la dimensión dividida).
2. Una vez que el algoritmo llega a un nodo hoja, verifica el punto del nodo y, si la distancia es mejor que la "mejor actual", ese punto del nodo se guarda como la "mejor actual".
3. El algoritmo desenrolla la recursión del árbol, realizando los siguientes pasos en cada nodo:
   1. Si el nodo actual está más cerca que el mejor actual, entonces se convierte en el mejor actual.
   2. El algoritmo comprueba si puede haber puntos en el otro lado del plano de división que estén más cerca del punto de búsqueda que el mejor punto actual. En teoría, esto se hace intersectando el hiperplano de división con una hiperesfera alrededor del punto de búsqueda que tiene un radio igual a la distancia más cercana actual. Dado que todos los hiperplanos están alineados con el eje, esto se implementa como una comparación simple para ver si la distancia entre la coordenada de división del punto de búsqueda y el nodo actual es menor que la distancia (coordenadas generales) desde el punto de búsqueda hasta el mejor punto actual.
      1. Si la hiperesfera cruza el plano, podría haber puntos más cercanos en el otro lado del plano, por lo que el algoritmo debe moverse hacia abajo por la otra rama del árbol desde el nodo actual en busca de puntos más cercanos, siguiendo el mismo proceso recursivo que toda la búsqueda.
      2. Si la hiperesfera no intersecta el plano de división, entonces el algoritmo continúa recorriendo el árbol y se elimina toda la rama del otro lado de ese nodo.
4. Cuando el algoritmo finaliza este proceso para el nodo raíz, la búsqueda estará completa.

Generalmente, el algoritmo utiliza distancias al cuadrado para la comparación a fin de evitar el cálculo de raíces cuadradas. Además, puede ahorrar cálculos al mantener la mejor distancia actual elevada al cuadrado en una variable para la comparación.

El algoritmo se puede ampliar de varias maneras mediante modificaciones simples. Puede proporcionar los k vecinos más cercanos a un punto manteniendo k mejores valores actuales en lugar de solo uno. Una rama solo se elimina cuando se han encontrado k puntos y la rama no puede tener puntos más cercanos que cualquiera de los k mejores valores actuales.

También se puede convertir en un algoritmo de aproximación para que se ejecute más rápido. Por ejemplo, la búsqueda aproximada del vecino más cercano se puede lograr simplemente estableciendo un límite superior en la cantidad de puntos a examinar en el árbol o interrumpiendo el proceso de búsqueda en función de un reloj de tiempo real (lo que puede ser más apropiado en implementaciones de hardware). El vecino más cercano para los puntos que ya están en el árbol se puede lograr al no actualizar el refinamiento para los nodos que dan una distancia cero. Como resultado, esto tiene la desventaja de descartar puntos que no son únicos pero que están ubicados junto con el punto de búsqueda original.

El vecino más cercano aproximado es útil en aplicaciones en tiempo real como la robótica debido al aumento significativo de velocidad que se obtiene al no buscar el mejor punto de manera exhaustiva. Una de sus implementaciones es la búsqueda best-bin-first .

Búsqueda de rango

Una búsqueda de rango busca rangos de parámetros. Por ejemplo, si un árbol almacena valores correspondientes a ingresos y edad, una búsqueda de rango podría ser algo así como buscar todos los miembros del árbol que tengan una edad entre 20 y 50 años y un ingreso entre 50.000 y 80.000. Dado que los árboles kd dividen el rango de un dominio a la mitad en cada nivel del árbol, son útiles para realizar búsquedas de rango.

Los análisis de árboles de búsqueda binaria han descubierto que el peor tiempo posible para la búsqueda de rango en un árbol k-d de dimensión k que contiene n nodos viene dado por la siguiente ecuación. ^[13]

${\displaystyle t_{\text{worst}}=O\left(k\cdot n^{1-{\frac {1}{k}}}\right)}$

Degradación del rendimiento con datos de alta dimensión

Encontrar el punto más cercano es una operación en promedio, en el caso de puntos distribuidos aleatoriamente, aunque el análisis en general es complicado. ^[14] ${\displaystyle O(\log(n))}$

En espacios de alta dimensión, la maldición de la dimensionalidad hace que el algoritmo necesite visitar muchas más ramas que en espacios de menor dimensión. En particular, cuando el número de puntos es apenas un poco mayor que el número de dimensiones, el algoritmo es apenas un poco mejor que una búsqueda lineal de todos los puntos. Como regla general, si la dimensionalidad es k , el número de puntos en los datos, n , debería ser . De lo contrario, cuando se utilizan árboles k -d con datos de alta dimensión, se evaluarán la mayoría de los puntos en el árbol y la eficiencia no es mejor que la de una búsqueda exhaustiva ^[15] y, si se requiere una respuesta lo suficientemente rápida, se deberían utilizar en su lugar métodos aproximados de vecino más cercano. ${\displaystyle n\gg 2^{k}}$

Degradación del rendimiento cuando el punto de consulta está lejos de los puntos en ela-d árbol

Además, incluso en un espacio de baja dimensión, si la distancia promedio por pares entre los k vecinos más cercanos del punto de consulta es significativamente menor que la distancia promedio entre el punto de consulta y cada uno de los k vecinos más cercanos, el rendimiento de la búsqueda del vecino más cercano se degrada hacia una linealidad, ya que las distancias desde el punto de consulta hasta cada vecino más cercano son de magnitud similar. (En el peor de los casos, considere una nube de puntos distribuidos en la superficie de una esfera centrada en el origen. Cada punto es equidistante del origen, por lo que una búsqueda del vecino más cercano desde el origen tendría que iterar a través de todos los puntos en la superficie de la esfera para identificar al vecino más cercano, que en este caso ni siquiera es único).

Para mitigar la posible degradación significativa del rendimiento de una búsqueda de árbol k -d en el peor de los casos, se puede proporcionar un parámetro de distancia máxima al algoritmo de búsqueda de árbol y la búsqueda recursiva se puede podar siempre que el punto más cercano en una rama dada del árbol no pueda estar más cerca que esta distancia máxima. Esto puede provocar que una búsqueda del vecino más cercano no devuelva un vecino más cercano, lo que significa que no hay puntos dentro de esta distancia máxima desde el punto de consulta.

Complejidad

• La construcción de un árbol k -d estático a partir de n puntos tiene la siguiente complejidad en el peor de los casos:
  • O ( n log ² n ) si se utiliza una ordenación O ( n log n ) como Heapsort o Mergesort para encontrar la mediana en cada nivel del árbol naciente;
  • O ( n log n ) si se utiliza un algoritmo de mediana de medianas O ( n ) ^{[5] [6]} para seleccionar la mediana en cada nivel del árbol naciente;
  • O ( kn log n ) si n puntos están preclasificados en cada una de las k dimensiones utilizando una clasificación O ( n log n ) como Heapsort o Mergesort antes de construir el árbol k -d . ^[10]
• Insertar un nuevo punto en un árbol k -d equilibrado toma un tiempo O (log n ) .
• Eliminar un punto de un árbol k- d equilibrado lleva un tiempo O (log n ) .
• La consulta de un rango paralelo al eje en un árbol k -d equilibrado toma un tiempo O ( n ^1−1/k + m ) , donde m es el número de puntos informados y k la dimensión del árbol k -d.
• Encontrar un vecino más cercano en un árbol k -d equilibrado con puntos distribuidos aleatoriamente toma un tiempo O (log n ) en promedio.

Variaciones

Objetos volumétricos

En lugar de puntos, un árbol k -d también puede contener rectángulos o hiperrectángulos . ^{[16] [17]} Por lo tanto, la búsqueda de rango se convierte en el problema de devolver todos los rectángulos que intersecan el rectángulo de búsqueda. El árbol se construye de la forma habitual con todos los rectángulos en las hojas. En una búsqueda de rango ortogonal , se utiliza la coordenada opuesta al comparar con la mediana. Por ejemplo, si el nivel actual se divide a lo largo de x _alto , verificamos la coordenada x _bajo del rectángulo de búsqueda. Si la mediana es menor que la coordenada x _bajo del rectángulo de búsqueda, entonces ningún rectángulo en la rama izquierda puede intersecar nunca con el rectángulo de búsqueda y, por lo tanto, puede podarse. De lo contrario, se deben recorrer ambas ramas. Véase también árbol de intervalos , que es un caso especial unidimensional.

Puntos solo en hojas

También es posible definir un árbol k -d con puntos almacenados únicamente en hojas. ^[4] Esta forma de árbol k -d permite una variedad de mecanismos de división distintos a la división mediana estándar. La regla de división de punto medio ^[18] selecciona en el medio del eje más largo del espacio que se está buscando, independientemente de la distribución de puntos. Esto garantiza que la relación de aspecto será como máximo 2:1, pero la profundidad depende de la distribución de puntos. Una variación, llamada punto medio deslizante, solo divide en el medio si hay puntos en ambos lados de la división. De lo contrario, divide en el punto más cercano al medio. Maneewongvatana y Mount muestran que esto ofrece un rendimiento "suficientemente bueno" en conjuntos de datos comunes.

Con el punto medio deslizante, se puede responder una consulta aproximada del vecino más cercano en . El conteo aproximado del rango se puede responder con este método. ${\displaystyle O\left({\tfrac {1}{{\epsilon \ }^{d}}}\log n\right)}$ ${\displaystyle O\left(\log n+{\left({\tfrac {1}{\epsilon \ }}\right)}^{d}\right)}$

Véase también

Variaciones cercanas:

• árbol k -d implícito , un árbol k -d definido por una función de división implícita en lugar de un conjunto de divisiones almacenadas explícitamente
• árbol k -d min/max , un árbol k -d que asocia un valor mínimo y máximo con cada uno de sus nodos
• Árbol k -d relajado , un árbol k -d tal que los discriminantes en cada nodo son arbitrarios

Variaciones relacionadas:

• Quadtree , una estructura de partición del espacio que se divide en dos dimensiones simultáneamente, de modo que cada nodo tiene 4 hijos
• Octree , una estructura de partición espacial que se divide en tres dimensiones simultáneamente, de modo que cada nodo tiene 8 hijos
• Árbol de bolas , una partición espacial multidimensional útil para la búsqueda del vecino más cercano
• Árbol R y jerarquía de intervalos delimitadores , estructura para particionar objetos en lugar de puntos, con regiones superpuestas
• Árbol de puntos de vista , una variante de un árbol k -d que utiliza hiperesferas en lugar de hiperplanos para particionar los datos

Problemas que se pueden solucionar con árboles k -d:

• Particionamiento recursivo , una técnica para construir árboles de decisión estadística que son similares a los árboles k -d
• Problema de medida de Klee , un problema de cálculo del área de una unión de rectángulos, solucionable utilizando árboles k -d
• Problema de la guillotina , un problema que consiste en encontrar un árbol k -d cuyas celdas sean lo suficientemente grandes como para contener un conjunto dado de rectángulos.

Implementaciones de código abierto

• ALGLIB tiene implementaciones en C# y C++ de algoritmos de vecino más cercano y vecino más cercano aproximado basados ​​en árboles k -d
• CGAL, la biblioteca de algoritmos computacionales, tiene implementaciones de algoritmos de búsqueda de rango, vecino más cercano aproximado y vecino más cercano basados ​​en árboles k -d.
• SciPy , una biblioteca de Python para computación científica, contiene implementaciones de algoritmos de búsqueda de vecino más cercano basados ​​en árboles k -d.
• scikit-learn , una biblioteca de Python para aprendizaje automático, contiene implementaciones de árboles k -d para respaldar búsquedas de vecinos más cercanos y vecinos de radio.

Referencias

1. "k-dimensional". xlinux.nist.gov . Consultado el 17 de septiembre de 2023 .
2. Hristov, Hristo (29 de marzo de 2023). "Introducción a los árboles KD". Baeldung .
3. Bentley, JL (1975). "Árboles de búsqueda binaria multidimensionales utilizados para búsqueda asociativa". Comunicaciones de la ACM . 18 (9): 509–517. doi : 10.1145/361002.361007 . S2CID  13091446.
4. Berg, Mark de; Cheong, Otfried; Kreveld, Marc van; Overmars, Mark (2008). "Búsqueda de rango ortogonal". Geometría computacional . págs. 95–120. doi :10.1007/978-3-540-77974-2_5. ISBN 978-3-540-77973-5.
5. Blum, M. ; Floyd, RW ; Pratt, VR ; Rivest, RL ; Tarjan, RE (agosto de 1973). "Límites de tiempo para la selección" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 7 (4): 448–461. doi : 10.1016/S0022-0000(73)80033-9 .
6. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. Introducción a los algoritmos . MIT Press y McGraw-Hill. Capítulo 10.
7. Wald I, Havran V (septiembre de 2006). "Sobre la construcción de árboles kd rápidos para trazado de rayos y sobre cómo hacerlo en O(N log N)" (PDF) . Simposio IEEE de 2006 sobre trazado de rayos interactivo . págs. 61–69. doi :10.1109/RT.2006.280216. ISBN . 1-4244-0693-5.S2CID1603250  .​
8. Havran V, Bittner J (2002). "Sobre la mejora de los árboles kd para la captura de rayos" (PDF) . En: Actas del WSCG : 209–216.
9. Procopiuc, T; Agarwal, M; Arge, L; Vittner, J (2003). "Bkd-tree: Un árbol kd dinámico y escalable". En Hadzilacos, T; Manolopoulos, Y; Roddick, J; Theodoridis, Y (eds.). Apuntes de clase en Ciencias de la Computación . Vol. 2750. Berlín: Springer-Verlag. págs. 46–65.
10. Brown R (2015). "Construcción de un árbol kd balanceado en tiempo O(kn log n)". Revista de técnicas gráficas por ordenador . 4 (1): 50–68.
11. Hristov, Hristo (29 de marzo de 2023). "Introducción a los árboles KD". Baeldung .
12. Chandran, Sharat. Introducción a los árboles kd. Departamento de Ciencias de la Computación de la Universidad de Maryland.
13. Lee, DT; Wong, CK (1977). "Análisis del peor caso para búsquedas de regiones y regiones parciales en árboles de búsqueda binarios multidimensionales y árboles cuadráticos balanceados". Acta Informatica . 9 . doi :10.1007/BF00263763. S2CID  36580055.
14. Freidman, JH ; Bentley, JL ; Finkel, RA (1977). "Un algoritmo para encontrar las mejores coincidencias en el tiempo esperado logarítmico". ACM Transactions on Mathematical Software . 3 (3): 209. doi :10.1145/355744.355745. OSTI  1443274. S2CID  10811510.
15. Jacob E. Goodman , Joseph O'Rourke y Piotr Indyk , ed. (2004). "Capítulo 39: Vecinos más próximos en espacios de alta dimensión". Manual de geometría discreta y computacional (2.ª ed.). CRC Press.
16. Rosenberg, JB (1985). "Estructuras de datos geográficos comparadas: un estudio de estructuras de datos que admiten consultas de regiones". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 4 : 53–67. doi :10.1109/TCAD.1985.1270098. S2CID  31223074.
17. Houthuys, P. (1987). "Box Sort, un método de ordenamiento binario multidimensional para cajas rectangulares, utilizado para búsquedas rápidas de rango". The Visual Computer . 3 (4): 236–249. doi :10.1007/BF01952830. S2CID  3197488.
18. S. Maneewongvatana y DM Mount . Está bien ser delgado si tus amigos son gordos. 4.º Taller anual de geometría computacional del CGC, 1999.