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 interior es igual al mínimo/máximo de los mínimos/máximos de sus hijos.
Los k d-trees mínimos/máximos pueden construirse recursivamente. Comenzando con el nodo raíz, se evalúa la orientación y posición del plano de división. Luego, los planos de división de los niños y los valores mínimos/máximos se evalúan recursivamente. El valor mínimo/máximo del nodo actual es simplemente el mínimo/máximo de los mínimos/máximos de sus hijos.
El min/max k dtree tiene - además de las propiedades de un kd-tree: la propiedad especial de que los valores mínimos/máximos de un nodo interno coinciden cada uno con un valor mínimo/máximo de cualquiera de los niños. Esto permite descartar el almacenamiento de valores mínimos/máximos en los nodos hoja almacenando dos bits en los nodos internos, asignando valores mínimos/máximos a los hijos: los valores mínimos/máximos de cada nodo interno se conocerán de antemano, mientras que el valor mínimo del nodo raíz Los valores /max se almacenan por separado. Cada nodo interno tiene además de dos valores mínimos/máximos, también dos bits dados, que definen a qué hijo se asignan esos valores mínimos/máximos (0: al hijo izquierdo 1: al hijo derecho). Los valores mínimos/máximos no asignados de los hijos son los valores mínimos/máximos ya conocidos del nodo actual. Los dos bits también pueden almacenarse en los bits menos significativos de los valores mínimo/máximo que, por lo tanto, deben aproximarse fraccionándolos hacia abajo/hacia arriba.
La reducción de memoria resultante no es menor, ya que los nodos hoja de k d-trees binarios completos son la mitad de los nodos del árbol.
Los k d-trees mín./máx . se utilizan para las isosuperficies de proyección de rayos /MIP ( proyección de máxima intensidad ). La emisión de rayos de isosuperficie solo atraviesa nodos para los que el isovalor elegido se encuentra entre los valores mínimos/máximos del nodo actual. Los nodos que no cumplen este requisito no contienen una isosuperficie para el isovalor dado y, por lo tanto, se omiten (omisión de espacios vacíos). Para MIP, los nodos no se atraviesan si su máximo es menor que la intensidad máxima actual a lo largo del rayo. La favorable complejidad de visualización de la emisión de rayos permite emitir rayos (e incluso cambiar la isosuperficie por) campos escalares muy grandes a velocidades de fotogramas interactivas en PC estándar. Especialmente implícito max k d-treesson una opción óptima para visualizar campos escalares definidos en cuadrículas rectilíneas (ver [1] [2] [3] ). De manera similar , se puede usar un árbol kd mínimo/máximo implícito para evaluar de manera eficiente consultas como la línea de visión del terreno . [4]