árbol Kd.pdf r6c2o

€rbol kd

1

€rbol kd En ciencias de la computaci‚n, un €rbol kd (abreviatura de •rbol k-dimensional) es una estructura de datos de particionado del espacio que organiza los puntos en un Espacio euclƒdeo de k dimensiones. Los •rboles kd son un caso especial de los •rboles BSP. Un •rbol kd emplea s‚lo planos perpendiculares a uno de los ejes del sistema de coordenadas. Esto difiere de los •rboles BSP, donde los planos pueden ser arbitrarios. Adem•s, todos los nodos de un •rbol kd, desde el nodo raƒz hasta los nodos hoja, almacenan un punto. Mientras tanto, en los •rboles BSP son las hojas los „nicos nodos que contienen puntos (u otras primitivas geom…tricas). Como consecuencia, cada plano debe pasar a trav…s de uno de los puntos del •rbol kd.

Un •rbol kd tridimensional. La primera divisi‚n (rojo) corta la celda raƒz (blanco) en dos subceldas, que son divididas a su vez (verde) en dos subceldas. Finalmente, cada una de esas cuatro es dividida (azul) en dos subceldas. Dado que no hay m•s divisiones, las ocho finales se llaman hojas. Las esferas amarillas representan los nodos del •rbol.

T…cnicamente, la letra k se refiere al n„mero de dimensiones. Un •rbol kd tridimensional podrƒa ser llamado un •rbol 3d. Sin embargo se suele emplear la expresi‚n "•rbol kd tridimensional". (Tambi…n es m•s descriptivo, ya que un •rbol tridimensional puede ser varias cosas, pero el t…rmino •rbol kd se refiere a un tipo en concreto de •rbol de particionado.) Las letras k y d se escriben en min„sculas, incluso al principio de una oraci‚n. La k se escribe en cursiva, aunque son tambi…n comunes las formas "•rbol KD" y "•rbol Kd".

Operaciones en •rboles k Construir un •rbol k Dado que hay muchas maneras posibles de elegir planos alineados a los ejes, hay muchas maneras de generar •rboles kd. El sistema habitual es: † Conforme se desciende en el •rbol, se emplean ciclos a trav…s de los ejes para seleccionar los planos. (Por ejemplo, la raƒz puede tener un plano alineado con el eje x, sus descendientes tendrƒan planos alineados con el y y los nietos del raƒz alineados con el z, y asƒ sucesivamente) † En cada paso, el punto seleccionado para crear el plano de corte ser• la mediana de los puntos puestos en el •rbol kd, lo que respeta sus coordenadas en el eje que est• siendo usado. Este m…todo lleva a un •rbol kd balanceado, donde cada nodo hoja est• a la misma distancia de la raƒz. De todas formas, los •rboles balanceados no son necesariamente ‚ptimos para todas las aplicaciones. Dada una lista de n puntos, el siguiente algoritmo genera un •rbol kd balanceado que contiene dichos puntos.

€rbol kd

2

function kdtree (list of points pointList, int depth) { if pointList is empty return nil; else { // Select axis based on depth so that axis cycles through all valid values var int axis := depth mod k; // Sort point list and choose median as pivot element sort pointList using predicate: point1[axis] < point2[axis]; choose median from pointList; // Create node and construct subtrees var tree_node node; node.location := median; node.leftChild := kdtree(points in pointList before median, depth+1); node.rightChild := kdtree(points in pointList after median, depth+1); return node; } }

Este algoritmo implementado en Python serƒa: class Node: def kdtree(pointList, depth=0): if not pointList: return # Select axis based on depth so that axis cycles through all valid values k = len(pointList[0]) # assumes all points have the same dimension axis = depth % k # Sort point list and choose median as pivot element pointList.sort(key=lambda x:x[axis]) median = len(pointList)/2 # choose median # Create node and construct subtrees node = Node() node.location = pointList[median] node.leftChild = kdtree(pointList[0:median], depth+1) node.rightChild = kdtree(pointList[median+1:], depth+1) return node Un ejemplo de uso:

€rbol kd pointList = [(2,3),(5,4),(9,1),(4,7),(8,1)] tree = kdtree(pointList) Este algoritmo crea el invariante para cualquier nodo. Todos los nodos en el sub•rbol de la izquierda est•n en un lado del plano de corte, y todos los nodos del sub•rbol de la derecha est•n en el otro lado. El plano de corte de un nodo pasa a trav…s del punto asociado con ese nodo (referenciado en el c‚digo por node.location)

A‚adir elementos a un •rbol kd Los nodos se a‡aden a un •rbol kd de la misma forma que se a‡aden a cualquier otro •rbol. Primero, se recorre el •rbol empezando por la raƒz y siguiendo por el nodo de la izquierda o de la derecha dependiendo de si el punto que se quiere insertar est• en la derecha o en la izquierda del plano de corte. Una vez que se llega a un nodo hoja, se a‡ade el nuevo punto a la izquierda o a la derecha del nodo hoja, de nuevo dependiendo de en que lado del plano se encuentra el nuevo punto.

Eliminar elementos de un •rbol kd Eliminar un punto de un •rbol kd sin romper el invariante. (POR HACER)

Equilibrar un •rbol kd Hay que ser cuidadoso al equilibrar un •rbol kd. Como estos •rboles est•n ordenados en m„ltiples dimensiones, no se puede emplear la t…cnica de rotaci‚n de •rboles para equilibrarlos € esto romperƒa el invariante.

Usos de un •rbol kd † Implementaci‚n en CBR ( Razonamiento Basado En Casos)

Bƒsqueda ortogonal en un •rbol kd Usar un •rbol kd para encontrar todos los puntos que se encuentran en un rect•ngulo determinado (o an•logo de m•s dimensiones). Esta operaci‚n tambi…n se denomina rango de b„squeda ortogonal.

Determinar d„nde evaluar una superficie En las regresiones locales es com„n evaluar la superficie contenida directamente s‚lo por los v…rtices del •rbol kd e interpolar en alg„n punto. Este uso, reflejado en la imagen de arriba, busca asegurar que s‚lo se realizar•n las evaluaciones directas necesarias. Como los •rboles kd se "adaptan" al espacio, este m…todo puede suministrar una excelente aproximaci‚n a las verdaderas superficies de regresi‚n local. Si la aproximaci‚n es pobre, puede mejorarse con m•s subdivisiones.

3

€rbol kd

Complejidad † Construir un •rbol kd est•tico a partir de n puntos es de O(nlogn). † Insertar un nuevo punto en un •rbol kd balanceado es de O(logn). † Eliminar un punto de un •rbol kd balanceado es de O(logn).

Enlaces externos (ingl…s) † C++ library that uses kd-trees for Approximate Nearest Neighbor Searching [1]

Referencias [1] http:/ / www. cs. umd. edu/ ~mount/ ANN/

4

Fuentes y contribuyentes del artƒculo

Fuentes y contribuyentes del art†culo €rbol kd ˆFuente: http://es.wikipedia.org/w/index.php?oldid=68575678 ˆContribuyentes: Airunp, Alvaro qc, CommonsDelinker, Dusan, Estructuras, GermanX, Khaine, Lasneyx, Petronas, Thorin, 13 ediciones an‚nimas

Fuentes de imagen, Licencias y contribuyentes Archivo:3dtree.png ˆFuente: http://es.wikipedia.org/w/index.php?title=Archivo:3dtree.png ˆLicencia: GNU General Public License ˆContribuyentes: Btyner, 2 ediciones an‚nimas

Licencia Creative Commons Attribution-Share Alike 3.0 //creativecommons.org/licenses/by-sa/3.0/

5