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í.

Algoritmy na stranách 22-24.

Tabule z 8. přednášky