Úloha lineárního programování

Dokončení omezené úlohy lineárního programování. Náhodnostní algoritmus. Střední hodnota náhodné veličiny. Očekávaná časová náročnost
je pouze O(n). Neomezená úloha lineárního programování.

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

Tabule ze 7. přednášky