k -d árbol

En informática , un k árbol -d (abreviatura de k dimensiones del árbol ) es una partición de espacio- estructura de datos para la organización de puntos en un k -dimensional espacio . 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 vecinos más cercanos ) y creación de nubes de puntos . Los árboles k -d son un caso especial de árboles de partición de espacio binario .

k -d árbol

Tipo

BST multidimensional

Inventado

1975

Inventado por

Jon Louis Bentley

Complejidad del tiempo en notación O grande

Algoritmo	Promedio	Peor de los casos
Espacio	${\ Displaystyle O (n)}$	${\ Displaystyle O (n)}$
Buscar	${\ Displaystyle O (\ log n)}$	${\ Displaystyle O (n)}$
Insertar	${\ Displaystyle O (\ log n)}$	${\ Displaystyle O (n)}$
Borrar	${\ Displaystyle O (\ log n)}$	${\ Displaystyle O (n)}$

Un árbol k- d tridimensional . La primera división (el plano vertical rojo) corta la celda raíz (blanca) en dos subcélulas, cada una de las cuales luego se divide (por los planos horizontales verdes) en dos subcélulas. Finalmente, cuatro celdas se dividen (por los cuatro planos verticales azules) en dos subcélulas. Como no hay más división, las ocho últimas se llaman células foliares.

Descripción

El árbol k -d es un árbol binario en el que cada nodo es un punto k -dimensional. Se puede pensar que cada nodo no hoja genera implícitamente un hiperplano que divide el espacio en dos partes, conocidas como medios espacios . 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 en 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 serán en el subárbol derecho. En tal caso, el hiperplano estaría establecido por el valor x del punto, y su normal sería la unidad del eje x. ^[1]

Operaciones en árboles k -d

Construcción

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

A medida que uno desciende 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 , los nietos de la raíz tendrían planos alineados con z, los bisnietos de la raíz tendrían todos tienen planos alineados con x, los tataranietos de la raíz tendrían 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 usa para crear el plano de división. (Tenga en cuenta la suposición de que alimentamos el conjunto completo de n puntos en el algoritmo por adelantado).

Este método conduce a un árbol k -d equilibrado , en el que cada nodo de la 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 medios, no hay garantía de que el árbol esté equilibrado. Para evitar codificar un algoritmo complejo de búsqueda de medianas de O ( n ) ^[3]^[4] o usar una ordenación O ( n log n ) como heapsort o mergesort para ordenar todos los n puntos, una práctica popular es ordenar un número fijo de puntos seleccionados al azar , y use 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.

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

función kdtree ( lista de puntos pointList, int profundidad){ // Seleccione el eje basado en la profundidad para que el eje recorra todos los valores válidos  var  int axis: = profundidad mod k; // Ordene la lista de puntos y elija la mediana como elemento pivote  seleccione la mediana por eje de pointList; // Crea un nodo y construye un subárbol node.location: = 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 los que son estrictamente mayores que la mediana. Para los puntos que se encuentran en la mediana, es posible definir una función de "superclave" que compara los puntos en todas las dimensiones ^{[ non sequitur ]} . En algunos casos, es aceptable dejar puntos iguales a la mediana en un lado de la mediana, por ejemplo, dividiendo los puntos en un subconjunto "menor que" y un subconjunto "mayor o igual que".

El algoritmo anterior implementado en el lenguaje de programación Python es el siguiente:

de  colecciones  importar  namedtuple del  operador  importar  itemgetter de  pprint  importar  pformatclass  Node ( namedtuple ( "Node" ,  "location left_child right_child" )):  def  __repr__ ( self ):  return  pformat ( tuple ( self ))def  kdtree ( lista_puntos ,  profundidad :  int  =  0 ):  si  no es  lista_puntos :  devuelve  Ninguno k  =  len ( point_list [ 0 ])  # asume que todos los puntos tienen la misma dimensión  # Seleccione el eje según la profundidad para que el eje recorra todos los valores válidos.  axis  =  depth  %  k # Ordene la lista de puntos por eje y elija mediana como elemento pivote  point_list . sort ( key = itemgetter ( eje ))  median  =  len ( point_list )  //  2 # Crear nodo y construir subárboles  return  Node (  location = point_list [ mediana ],  left_child = kdtree ( point_list [: mediana ],  profundidad  +  1 ),  right_child = kdtree ( point_list [ mediana  +  1  :],  profundidad  +  1 ),  )def  main ():  "" "Ejemplo de uso" ""  point_list  =  [( 7 ,  2 ),  ( 5 ,  4 ),  ( 9 ,  6 ),  ( 4 ,  7 ),  ( 8 ,  1 ),  ( 2 ,  3 )]  árbol  =  kdtree ( lista_puntos )  print ( árbol )if  __name__  ==  "__main__" :  main ()

La salida sería:

((7, 2), ((5, 4), ((2, 3), Ninguno, Ninguno), ((4, 7), Ninguno, Ninguno)), ((9, 6), ((8, 1), Ninguno, Ninguno), Ninguno))

El árbol generado se muestra a continuación.

k -d descomposición del árbol para el conjunto de puntos
(2,3), (5,4), (9,6), (4,7), (8,1), (7,2).

El árbol k -d resultante .

Este algoritmo crea el invariante de que para cualquier nodo, todos los nodos en el subárbol izquierdo están en un lado de un plano de división y todos los nodos en el 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 (denominado en el código como node.location ).

Algoritmos alternativos para construir un árbol k -d balanceado clasifican previamente los datos antes de construir el árbol. Luego, mantienen el orden de 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 de computadora tridimensionales . Estos algoritmos preordenan n triángulos antes de construir el árbol k -d , luego construyen el árbol en tiempo O ( n log n ) en el mejor de los casos. ^[5]^[6] Un algoritmo que construye un árbol k -d balanceado para ordenar puntos tiene una complejidad en el peor de los casos de O ( kn log n ) . ^[7]^[8] Este algoritmo presorts n puntos en cada uno de k dimensiones utilizando un O ( n log n ) tipo tales como heapsort o por fusión antes de construir el árbol. Luego, mantiene el orden de estos k preselecciones durante la construcción del árbol y, por lo tanto, evita encontrar la mediana en cada nivel de subdivisió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, atraviese el árbol, comenzando desde la raíz y moviéndose hacia la izquierda o hacia la derecha, 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 debajo del 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 árbol. La tasa de degradación del rendimiento de los árboles 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.

Eliminar 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 de destino y volver a crear esa parte del árbol.

Otro enfoque es encontrar un reemplazo para el punto eliminado. ^[9] Primero, busque el nodo R que contiene el punto 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 p, del subárbol con raíz en R. Reemplace el punto almacenado en R con p. Luego, elimine de forma recursiva p.

Para encontrar un punto de reemplazo, si R discrimina en x (digamos) y R tiene un hijo correcto, encuentre el punto con el valor mínimo de x del subárbol enraizado en el hijo correcto. De lo contrario, busque el punto con el valor x máximo del subárbol enraizado en el hijo izquierdo.

Equilibrio

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

Existen varias variantes de árboles k -d equilibrados . Incluyen 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

"> Reproducir medios

Ejemplo de búsqueda de un vecino más cercano en un árbol 2-d. Aquí, el árbol ya está construido, cada nodo corresponde a un rectángulo, cada rectángulo se divide 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 dado. Esta búsqueda se puede realizar de manera eficiente mediante el uso de 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 procede de la siguiente manera:

Comenzando con el nodo raíz, el algoritmo se mueve hacia abajo 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).
Una vez que el algoritmo llega a un nodo hoja, comprueba ese punto de nodo y si la distancia es mejor, ese punto de nodo se guarda como el "mejor actual".
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 verifica 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 cruzando el hiperplano que se divide 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 al mejor 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 descender 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 se cruza con el plano de división, el algoritmo continúa subiendo por el árbol y se elimina toda la rama del otro lado de ese nodo.
Cuando el algoritmo finaliza este proceso para el nodo raíz, la búsqueda está completa.

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

El algoritmo se puede ampliar de varias formas mediante modificaciones sencillas. Puede proporcionar los k vecinos más cercanos a un punto manteniendo k 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 cerca que cualquiera de los k mejores actuales.

También se puede convertir a un algoritmo de aproximación para que se ejecute más rápido. Por ejemplo, la búsqueda de vecino más cercano aproximado se puede lograr simplemente estableciendo un límite superior en el número de puntos para examinar en el árbol, o interrumpiendo el proceso de búsqueda basado 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 al no actualizar el refinamiento para los nodos que dan como resultado una distancia cero, 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 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 está almacenando 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 los árboles de búsqueda binaria 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. ^[10]

{\ Displaystyle t _ {\ text {peor}} = 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 O (log n ) en promedio, en el caso de puntos distribuidos aleatoriamente, aunque el análisis en general es complicado. ^[11]

En espacios de alta dimensión, la maldición de la dimensionalidad hace que el algoritmo necesite visitar muchas más ramas que en los espacios de menor dimensión. En particular, cuando el número de puntos es solo un poco más alto que el número de dimensiones, el algoritmo es solo 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 , debe ser n ≫ 2 ^k . De lo contrario, cuando se utilizan árboles k -d con datos de alta dimensión, la mayoría de los puntos del árbol serán evaluados y la eficiencia no es mejor que la búsqueda exhaustiva, ^[12] y, si se requiere una respuesta rápida suficientemente buena, En su lugar, deben usarse métodos aproximados del vecino más cercano.

Degradación en el 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 media por pares entre los k vecinos más cercanos del punto de consulta es significativamente menor que la distancia media 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 iterar a través de 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 del rendimiento potencialmente significativa 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 determinada del árbol no puede estar más cerca que esta distancia máxima. Esto puede provocar que la búsqueda de un 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 un O ( n log n ) tipo tales como heapsort o por fusión se utiliza para encontrar la mediana en cada nivel del árbol naciente;
- O ( n log n ) si se utiliza un algoritmo de O ( n ) mediana de medianas ^[3]^[4] para seleccionar la mediana en cada nivel del árbol naciente;
- O ( kn log n ) si n puntos se han clasificado previamente en cada uno de k dimensiones utilizando un O ( n log n ) tipo tales como heapsort o por fusión antes de la construcción de la k árbol -d . ^[8]
Insertar un nuevo punto en un árbol k -d balanceado toma O (log n ) tiempo.
Eliminar un punto de un árbol k -d equilibrado toma O (log n ) tiempo.
Consultar un rango de ejes paralelos en un árbol k -d balanceado toma O ( n ^{1−1 / k} + m ) tiempo, donde m es el número de puntos reportados yk la dimensión del árbol k -d.
Encontrar 1 vecino más cercano en un árbol k -d equilibrado con puntos distribuidos aleatoriamente toma 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 . ^[13]^[14] Por lo tanto, la búsqueda de rango se convierte en el problema de devolver todos los rectángulos que se cruzan con 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 usa 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 _baja 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 puede cruzarse con el rectángulo de búsqueda y, por lo tanto, puede 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 hojas. ^[2] Esta forma de árbol k -d permite una variedad de mecánicas de división distintas de la división mediana estándar. La regla de división del punto medio ^[15] selecciona en el medio 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 en el medio si hay puntos en ambos lados de la división. De lo contrario, se 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.

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

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 k -d árbol que asocia un valor mínimo y máximo con cada uno de sus nodos
Árbol k -d relajado , un árbol k -d en el que los discriminantes en cada nodo son arbitrarios

Variaciones relacionadas:

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

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

Partición recursiva , 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, que se puede resolver usando k -d árboles
Problema de guillotina , un problema de 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 aproximados basados en árbol k -d
SciPy , una biblioteca de Python para computación científica, contiene implementaciones de algoritmos de búsqueda de vecinos más cercanos basados en árboles k -d.
scikit-learn , una biblioteca de Python para el aprendizaje automático, contiene implementaciones de árboles k -d para respaldar las búsquedas de vecinos de radio y vecinos más cercanos.

Referencias

^ Bentley, JL (1975). "Árboles de búsqueda binarios multidimensionales utilizados para búsqueda asociativa". Comunicaciones de la ACM . 18 (9): 509–517. doi : 10.1145 / 361002.361007 . S2CID 13091446 .
^ a b 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.
^ a b 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 Sistemas . 7 (4): 448–461. doi : 10.1016 / S0022-0000 (73) 80033-9 .
^ a b Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. Introducción a los algoritmos . MIT Press y McGraw-Hill. Capítulo 10.
^ Wald I, Havran V (septiembre de 2006). "Sobre la construcción de árboles kd rápidos para el trazado de rayos y sobre cómo hacerlo en O (N log N)" (PDF) . En: Actas del Simposio IEEE de 2006 sobre trazado de rayos interactivo : 61–69. doi : 10.1109 / RT.2006.280216 . ISBN 1-4244-0693-5. S2CID 1603250 .
^ Havran V, Bittner J (2002). "Sobre la mejora de los árboles kd para la captura de rayos" (PDF) . En: Proceedings of the WSCG : 209–216.
^ Procopiuc, T; Agarwal, M; Arge, L; Vittner, J (2003). "Bkd-tree: un árbol kd dinámico escalable". En Hadzilacos, T; Manolopoulos, Y; Roddick, J; Theodoridis, Y (eds.). Apuntes de conferencias en Ciencias de la Computación . 2750 . Berlín: Springer-Verlag. págs. 46–65.
^ a b Brown R (2015). "Construyendo un árbol k -d balanceado en tiempo O ( kn log n ) " . Revista de técnicas de infografía . 4 (1): 50–68.
^ Chandran, Sharat. Introducción a los árboles kd . Departamento de Ciencias de la Computación de la Universidad de Maryland.
^ 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 binaria multidimensionales y árboles cuádruples equilibrados". Acta Informatica . 9 . doi : 10.1007 / BF00263763 . S2CID 36580055 .
^ Freidman, JH ; Bentley, JL ; Finkel, RA (1977). "Un algoritmo para encontrar las mejores coincidencias en el tiempo esperado logarítmico". Transacciones ACM en software matemático . 3 (3): 209. doi : 10.1145 / 355744.355745 . OSTI 1443274 . S2CID 10811510 .
^ 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.
^ Rosenberg, JB (1985). "Estructuras de datos geográficos comparadas: un estudio de las estructuras de datos que apoyan las consultas de la región". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 4 : 53–67. doi : 10.1109 / TCAD.1985.1270098 . S2CID 31223074 .
^ Houthuys, P. (1987). "Box Sort, un método de clasificación binario multidimensional para cajas rectangulares, utilizado para búsqueda de rango rápido". La computadora visual . 3 (4): 236–249. doi : 10.1007 / BF01952830 . S2CID 3197488 .
^ S. Maneewongvatana y DM Mount . Está bien ser flaco, si tus amigos son gordos . Cuarto Taller Anual de CGC sobre Geometría Computacional, 1999.

[1] Bentley, JL (1975). "Árboles de búsqueda binarios multidimensionales utilizados para búsqueda asociativa". Comunicaciones de la ACM . 18 (9): 509–517. doi : 10.1145 / 361002.361007 . S2CID 13091446 .

[compgeom-2] 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.

[blum-3] 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 Sistemas . 7 (4): 448–461. doi : 10.1016 / S0022-0000 (73) 80033-9 .

[cormen-4] Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. Introducción a los algoritmos . MIT Press y McGraw-Hill. Capítulo 10.

[5] Wald I, Havran V (septiembre de 2006). "Sobre la construcción de árboles kd rápidos para el trazado de rayos y sobre cómo hacerlo en O (N log N)" (PDF) . En: Actas del Simposio IEEE de 2006 sobre trazado de rayos interactivo : 61–69. doi : 10.1109 / RT.2006.280216 . ISBN 1-4244-0693-5. S2CID 1603250 .

[6] Havran V, Bittner J (2002). "Sobre la mejora de los árboles kd para la captura de rayos" (PDF) . En: Proceedings of the WSCG : 209–216.

[7] Procopiuc, T; Agarwal, M; Arge, L; Vittner, J (2003). "Bkd-tree: un árbol kd dinámico escalable". En Hadzilacos, T; Manolopoulos, Y; Roddick, J; Theodoridis, Y (eds.). Apuntes de conferencias en Ciencias de la Computación . 2750 . Berlín: Springer-Verlag. págs. 46–65.

[knlogn-8] Brown R (2015). "Construyendo un árbol k -d balanceado en tiempo O ( kn log n ) " . Revista de técnicas de infografía . 4 (1): 50–68.

[9] Chandran, Sharat. Introducción a los árboles kd . Departamento de Ciencias de la Computación de la Universidad de Maryland.

[Lee1977-10] 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 binaria multidimensionales y árboles cuádruples equilibrados". Acta Informatica . 9 . doi : 10.1007 / BF00263763 . S2CID 36580055 .

[Friedman:1977:AFB:355744.355745-11] Freidman, JH ; Bentley, JL ; Finkel, RA (1977). "Un algoritmo para encontrar las mejores coincidencias en el tiempo esperado logarítmico". Transacciones ACM en software matemático . 3 (3): 209. doi : 10.1145 / 355744.355745 . OSTI 1443274 . S2CID 10811510 .

[12] 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.

[13] Rosenberg, JB (1985). "Estructuras de datos geográficos comparadas: un estudio de las estructuras de datos que apoyan las consultas de la región". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 4 : 53–67. doi : 10.1109 / TCAD.1985.1270098 . S2CID 31223074 .

[14] Houthuys, P. (1987). "Box Sort, un método de clasificación binario multidimensional para cajas rectangulares, utilizado para búsqueda de rango rápido". La computadora visual . 3 (4): 236–249. doi : 10.1007 / BF01952830 . S2CID 3197488 .

[midpointsplit-15] S. Maneewongvatana y DM Mount . Está bien ser flaco, si tus amigos son gordos . Cuarto Taller Anual de CGC sobre Geometría Computacional, 1999.

[1]