Árbol kd mínimo/máximo

Un árbol k d min/max es un árbol k d con dos valores escalares —un mínimo y un máximo— asignados a sus nodos. El mínimo/máximo de un nodo interno es igual al mínimo/máximo de los mínimos/máximos de sus hijos.

Los árboles d de k valores mínimos y máximos se pueden construir recursivamente. Partiendo del nodo raíz, se evalúa la orientación y la posición del plano de división. A continuación, se evalúan recursivamente los planos de división y los valores mínimos y máximos de los nodos hijos. El valor mínimo y máximo del nodo actual es simplemente el mínimo y el máximo de los mínimos y máximos de sus hijos.

El árbol k d min/max posee, además de las propiedades de un árbol k d, la particularidad de que los valores min/max de un nodo interno coinciden con los valores min/max de cualquiera de sus hijos. Esto permite prescindir del almacenamiento de valores min/max en los nodos hoja, almacenando dos bits en los nodos internos que asignan dichos valores a los hijos: los valores min/max de cada nodo interno se conocen de antemano, mientras que los del nodo raíz se almacenan por separado. Cada nodo interno dispone, además de dos valores min/max, de dos bits que definen a qué hijo se asignan (0: al hijo izquierdo; 1: al hijo derecho). Los valores min/max no asignados a los hijos son los valores min/max ya conocidos del nodo actual. Estos dos bits también pueden almacenarse en los bits menos significativos de los valores min/max, que deben aproximarse mediante fraccionamiento.

La reducción de memoria resultante no es insignificante, ya que los nodos hoja de los árboles d binarios k completos representan la mitad de los nodos del árbol.

Los árboles k d min/max se utilizan para la proyección de isosuperficies / MIP ( proyección de máxima intensidad ) mediante trazado de rayos. El trazado de rayos sobre isosuperficies solo recorre los nodos cuyo isovalor elegido se encuentra entre los valores min/max del nodo actual. Los nodos que no cumplen este requisito no contienen una isosuperficie para el isovalor dado y, por lo tanto, se omiten (salto de espacio vacío). Para MIP, los nodos no se recorren si su máximo es menor que la intensidad máxima actual a lo largo del rayo. La favorable complejidad de visualización del trazado de rayos permite trazar (e incluso cambiar la isosuperficie para) campos escalares muy grandes a velocidades de fotogramas interactivas en PCs convencionales. En particular, los árboles k d max implícitos son una opción óptima para visualizar campos escalares definidos en cuadrículas rectilíneas (véase ^{[ 1 ] [ 2 ] [ 3 ]} ). De manera similar, un árbol k d min/max implícito puede utilizarse para evaluar de forma eficiente consultas como la línea de visión del terreno . ^{[ 4 ]}

• árbol k -d
• árbol k d implícito