árbol kd

Árbol de búsqueda multidimensional de puntos en un espacio de k dimensiones.

En informática , un árbol k -d (abreviatura de árbol k-dimensional ) es una estructura de datos de partición espacial para organizar puntos en un espacio k -dimensional . K-dimensional es aquello 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, tales 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 ) &
• 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 k -dimensional. ^[2] Se puede pensar que cada nodo que no es hoja genera implícitamente un hiperplano de división 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 k dimensiones, 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 aparecerán en el subárbol izquierdo. estar 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 en árboles k -d

Construcción

Dado que hay 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 baja por el árbol, recorre 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 planos alineados con y , todos los nietos de la raíz tendrían planos alineados con z , los bisnietos de la raíz tendrían todos tendrían 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 ingresamos el conjunto completo de n puntos en el algoritmo desde el principio).

Este método conduce a un árbol k -d equilibrado , en el que cada nodo de hoja está 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 los puntos medianos, 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 usar una clasificación como heapsort o mergesort para ordenar los n puntos, una práctica popular es ordenar un número fijo de puntos seleccionados aleatoriamente y usar la mediana de esos puntos para servir como plano de división. En la práctica, esta técnica suele dar como resultado árboles muy equilibrados. ${\displaystyle O(n)}$ ${\displaystyle O(n\log(n))}$

Dada una lista de n puntos, el siguiente algoritmo utiliza una clasificación de búsqueda de mediana para construir un árbol k -d equilibrado que contenga esos puntos.

función kdtree ( lista de puntos pointList, int profundidad){ // Seleccione el eje según la profundidad para que el eje recorra todos los valores válidos  var  int axis := profundidad mod k; // Ordena la lista de puntos y elige la mediana como elemento pivote  selecciona la mediana por eje de 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); nodo de retorno ;}

Es común que los puntos "después" de la mediana incluyan sólo 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 a ambos 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 nodo.ubicación ).

Algoritmos alternativos para construir un árbol k -d equilibrado preclasificar los datos antes de construir el árbol. Luego, mantienen el orden de la clasificación previa 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 por computadora tridimensionales . Estos algoritmos ordenan previamente 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 preclasifica n puntos en cada una de las k dimensiones utilizando una clasificación como Heapsort o Mergesort antes de construir el árbol. Luego mantiene el orden de estos k preordenamientos 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))}$

Agregar 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 a insertar está en el lado "izquierdo" o "derecho" del plano de división. Una vez que llegue al nodo bajo el cual debe ubicarse el hijo, agregue el nuevo punto como hijo izquierdo o derecho del nodo hoja, nuevamente dependiendo de qué lado del plano de división del nodo contiene el nuevo nodo.

Agregar puntos de esta manera puede hacer que el árbol se desequilibre, lo que provocará una disminución del rendimiento del mismo. La tasa de degradación del rendimiento del árbol depende de la distribución espacial de los puntos del árbol que se agregan y del número 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.

Eliminando elementos

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

Otro enfoque es encontrar un reemplazo para el punto eliminado. ^[12] Primero, busque el nodo que contiene el punto que se va a eliminar. Para el caso base, donde R es un nodo hoja, no se requiere reemplazo. Para el caso general, busque 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 (digamos) y tiene un hijo correcto, encuentre el punto con el valor mínimo del subárbol con raíz en el hijo correcto. De lo contrario, busque 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 clasifican en múltiples dimensiones, por lo que la técnica de rotación de árboles no se puede utilizar para equilibrarlos, ya que esto puede romper la invariante.

Existen varias variantes de árboles k -d equilibrados. Incluyen árbol k -d dividido, pseudo árbol k -d, árbol KDB , árbol hB y árbol Bkd . Muchas de estas variantes son árboles kd adaptativos .

Búsqueda de vecino más cercano

Ejemplo de búsqueda de vecino más cercano en un árbol bidimensional. 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 solo punto.

El algoritmo de búsqueda de vecino más cercano (NN) tiene como objetivo encontrar el punto en el árbol más cercano 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 baja en el árbol de forma recursiva, de la misma manera que lo haría si se estuviera insertando el punto de búsqueda (es decir, va hacia la izquierda o hacia 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 el "mejor actual", ese punto del nodo se guarda como el "mejor actual".
3. El algoritmo desenrolla la recursividad 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 podría 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 actual. En concepto, 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 los ejes, 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 actual.
      1. Si la hiperesfera cruza el plano, podría haber puntos más cercanos al otro lado del plano, por lo que el algoritmo debe bajar por la otra rama del árbol desde el nodo actual buscando 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 subiendo por 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 se completa.

Generalmente, el algoritmo utiliza distancias al cuadrado para comparar y evitar calcular raíces cuadradas. Además, puede ahorrar cálculos al mantener la mejor distancia actual al cuadrado en una variable para comparar.

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 actuales en lugar de solo uno. Una rama sólo se elimina cuando se han encontrado k puntos y la rama no puede tener puntos más cerca que cualquiera de los k mejores actuales.

También se puede convertir en un algoritmo de aproximación para ejecutarlo 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 el número de puntos a examinar en el árbol o interrumpiendo el proceso de búsqueda basándose en un reloj de tiempo real (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 no actualizando 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 al punto de búsqueda original.

El vecino más cercano aproximado es útil en aplicaciones en tiempo real como la robótica debido al importante aumento de velocidad que se obtiene al no buscar exhaustivamente el mejor punto. 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, entonces 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 binarios han encontrado que el peor momento para la búsqueda de rango en un árbol k -dimensional k -d 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 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 sólo ligeramente mayor que el número de dimensiones, el algoritmo es sólo ligeramente 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 , debe ser . De lo contrario, cuando se utilizan árboles k -d con datos de alta dimensión, la mayoría de los puntos del árbol se evaluarán y la eficiencia no es mejor que la búsqueda exhaustiva ^[15] y, si se requiere una respuesta lo suficientemente buena y rápida, En su lugar, se deben utilizar métodos aproximados del vecino más cercano. ${\displaystyle n\gg 2^{k}}$

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

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 lineal, ya que las distancias desde el punto de consulta a 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 la búsqueda del vecino más cercano al origen tendría que recorrer todos los puntos del origen. superficie de la esfera para identificar al vecino más cercano, que en este caso ni siquiera es único).

Para mitigar la degradación potencialmente 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 se encuentre el punto más cercano en una rama determinada del árbol. no puede estar más cerca que esta distancia máxima. Esto puede provocar que una búsqueda de 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

• Construir 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 clasificació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 O ( n ) de mediana de medianas ^{[5] [6]} para seleccionar la mediana en cada nivel del árbol naciente;
  • O ( kn log n ) si n puntos se preordenan en cada una de las k dimensiones usando 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 requiere tiempo O (log n ) .
• Eliminar un punto de un árbol k -d equilibrado requiere tiempo O (log n ) .
• Consultar un rango paralelo al eje en un árbol k -d equilibrado lleva O ( n ^1−1/k + m ) tiempo, donde m es el número de puntos informados y k la dimensión del árbol k -d.
• Encontrar 1 vecino más cercano en un árbol k -d equilibrado con puntos distribuidos aleatoriamente lleva O (log n ) tiempo 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 cruzan 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 cuando se compara 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 _baja del rectángulo de búsqueda, entonces ningún rectángulo en la rama izquierda podrá cruzarse con el rectángulo de búsqueda y, por lo tanto, podrá podarse. De lo contrario, se deben atravesar 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 las hojas. ^[4] Esta forma de árbol k -d permite una variedad de mecanismos de división distintos de la división mediana estándar. La regla de división del punto medio ^[18] selecciona en la mitad del eje más largo del espacio que se busca, 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 se divide por la mitad si hay puntos en ambos lados de la división. De lo contrario, se divide en el punto más cercano al centro. Maneewongvatana y Mount muestran que esto ofrece un rendimiento "suficientemente bueno" en conjuntos de datos comunes.

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

Ver 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 almacenado explícitamente
• min/max k -d tree , un árbol k -d que asocia un valor mínimo y máximo a 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 espacial 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
• Ball tree , 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 dividir objetos en lugar de puntos, con regiones superpuestas
• Árbol de punto de vista , una variante de un árbol k -d que utiliza hiperesferas en lugar de hiperplanos para particionar los datos.

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

• Partición recursiva , una técnica para construir árboles de decisión estadísticos similares a los árboles k -d
• Problema de medida de Klee , un problema de calcular el área de una unión de rectángulos, que se puede resolver usando árboles k -d
• Problema de guillotina , un problema de encontrar un árbol k -d cuyas celdas sean lo suficientemente grandes como para contener un conjunto determinado de rectángulos.

Implementaciones de código abierto

• ALGLIB tiene implementaciones en C# y C++ de algoritmos de vecino más cercano basados ​​en árbol k -d y de vecino más cercano aproximado
• CGAL, la biblioteca de algoritmos computacionales, tiene implementaciones de vecino más cercano basado en árbol k -d, vecino más cercano aproximado y algoritmos de búsqueda de rango.
• SciPy , una biblioteca de Python para informática 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 las búsquedas de vecinos más cercanos y 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 multidimensional 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). «Plazos de 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 kd-Trees rápidos para Ray Tracing y 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. S2CID  1603250.
8. Havran V, Bittner J (2002). "Sobre la mejora de los árboles kd para la captura de rayos" (PDF) . En: Actas de la WSCG : 209–216.
9. Procopiuc, T; Agarwal, M; Arge, L; Vittner, J (2003). "Bkd-tree: un kd-tree dinámico escalable". En Hadzilacos, T; Manolopoulos, Y; Roddick, J; Theodoridis, Y (eds.). Apuntes de conferencias sobre informática . vol. 2750. Berlín: Springer-Verlag. págs. 46–65.
10. Brown R (2015). "Construcción de un árbol kd equilibrado en tiempo O (kn log n)". Revista de técnicas de infografía . 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 de los casos para búsquedas de regiones y regiones parciales en árboles de búsqueda binarios multidimensionales y árboles cuádruples equilibrados". Acta Informática . 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". Transacciones ACM sobre software matemático . 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 cercanos en espacios de alta dimensión". Manual de geometría discreta y computacional (2ª ed.). Prensa CRC.
16. Rosenberg, JB (1985). "Comparación de estructuras de datos geográficos: un estudio de estructuras de datos que respaldan consultas regionales". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 4 : 53–67. doi :10.1109/TCAD.1985.1270098. S2CID  31223074.
17. Houthuys, P. (1987). "Box Sort, un método de clasificación binaria multidimensional para cajas rectangulares, utilizado para búsquedas rápidas de rango". La computadora visual . 3 (4): 236–249. doi :10.1007/BF01952830. S2CID  3197488.
18. S. Maneewongvatana y DM Mount . Está bien ser flaco si tus amigos son gordos. Cuarto Taller Anual del CGC sobre Geometría Computacional, 1999.