Ortogonální vyhledávání

Motivace, vhodné deatové struktury jsou kd-stromy a range-trees. 1-dimenzionální vyhledávání. Vyvážený binární strom, v něm hledáme všechy listy ležící v intervalu [x,x`]. Split vrchol, algoritmy FIND SPLIT NODE a 1D RANGE QUERY. Vybudování stromu O(nlog n), vyhledávání O(log n+k), kde k je počet vyhledaných bodů, paměť O(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 následujícího souboru

Tabule ze 7. přednášky