Ortogonální vyhledávání: kd-stromy 

Které body z dané množiny leží v obdélníku [x,x`]x[y,y`]. Konstrukce kd-stromu, geometrická motivace, algoritmus BUILD kd-TREE (P, depth). Čas konstrukce O(nlog n), paměť O(n).Region uzlu, algoritmus SEARCH kd-TREE typu rozděl a panuj, rekurentní formule pro vyhledávací čas dává čas vyhledání O(n^1/2+k). Odstranění zjednodušujících předpokladů na souřadnice bodů z množiny P vede k lexikografickému uspořádání.

Range trees

Strom podle x-ové souřadnice, ke každému podstromu T(v) asociovaný strom T_ass(v) podle y-ové souřadnice. Paměť O(nlog n). Algoritmus BUILD 2D RANGE TREE. časová náročnost O(n log n). Vyhledávání nejprve podle souřadnice x a potom podle y, algoritmus 2D RANGE QUERY, vyhledávací čas O(log²n+k). V d dimenzích potřebujeme paměť O(n log^d-1n), čas pro konstrukci O(n log^d-1n) a čas pro vyhledání O(log^dn+k). 

Tabule z 8. přednášky