Albero k-d

In generale la direzione dell'iperpiano viene scelta nel modo seguente: ogni nodo dell’albero è associato a una delle k dimensioni, con l'iperpiano perpendicolare all’asse di quella dimensione. Quindi, ad esempio, se per una particolare divisione viene scelto l’asse “x”, tutti i punti nel sottoalbero con un valore di “x” inferiore a quello del nodo appariranno nel sottoalbero sinistro e tutti i punti con un valore di “x” maggiore saranno nel sottoalbero destro. In tal caso, l'iperpiano sarebbe determinato dal valore di x del punto e la sua normale sarebbe l’asse x unitario.^[5] La scelta dell'asse di divisione e del punto di partizionamento (split) varia a seconda dell'implementazione, ma l'approccio standard (proposto da Bentley) segue queste regole:

• Rotazione degli assi: si seleziona l'asse di divisione in base alla profondità del nodo nell'albero. Ad esempio, in uno spazio tridimensionale (k=3), la radice divide lungo l'asse x (profondità 0), il livello successivo lungo l'asse y (profondità 1), quello dopo lungo l'asse z (profondità 2), per poi ricominciare dall'asse x (profondità 3). In generale, l'asse è dato da:

${\displaystyle {\textit {asse}}={\textit {profondit}}{\grave {a}}\mod k}$

• Scelta della mediana: per garantire che l'albero sia bilanciato, il punto di split viene scelto calcolando la mediana delle coordinate dei punti lungo l'asse selezionato.

La costruzione di un albero k-d a partire da un insieme di N punti avviene in modo ricorsivo:

• Si seleziona l'asse corrente.
• Si ordina il set di punti in base alla coordinata dell'asse e si trova la mediana.
• Il punto mediano diventa il nodo corrente.
• Si applica la procedura ricorsivamente sui punti a sinistra e a destra della mediana.

Se la mediana viene calcolata in tempo lineare utilizzando un algoritmo come Quickselect, il tempo di costruzione totale è ottimale e pari a ${\displaystyle {\mathcal {O}}(N\log N)}$.

La ricerca del vicino più prossimo o NNS (Nearest Neighbor Search) mira a trovare il punto nell'albero più vicino a un punto di query Q. L'algoritmo sfrutta le proprietà geometriche dell'albero per eliminare ("potare") interi rami senza doverli esplorare:

• Discesa: si scende attraverso l'albero come in una normale ricerca binaria per trovare la foglia in cui si troverebbe Q;
• Salita e Verifica: si calcola la distanza tra Q e il punto corrente. Se è inferiore alla distanza minima attuale, diventa il nuovo "migliore";
• Potatura: prima di risalire al nodo padre, l'algoritmo controlla se l'iperpiano di divisione del nodo interseca una sfera ipotetica centrata in Q con raggio pari alla distanza minima corrente; se non c'è intersezione, l'intero sottoalbero opposto viene scartato, garantendo un grande risparmio computazionale.

La complessità delle operazioni su un albero k-d dipende fortemente dal bilanciamento dell'albero e dal numero di dimensioni k:

Operazione	Caso Ottimo / Medio	Caso Peggiore
Spazio di memoria	${\displaystyle {\mathcal {O}}(N)}$	${\displaystyle {\mathcal {O}}(N)}$
Costruzione	${\displaystyle {\mathcal {O}}(N\log N)}$	${\displaystyle {\mathcal {O}}(N\log N)}$ [c 1]
Ricerca NNS	${\displaystyle {\mathcal {O}}(\log N)}$	${\displaystyle {\mathcal {O}}(N)}$
Query di intervallo	${\displaystyle {\mathcal {O}}(N^{1-{\tfrac {1}{k}}}+M)}$[c 2]	${\displaystyle {\mathcal {O}}(N)}$