Geometrické algoritmy

8. přednáška

Ortogonální vyhledávání - range trees

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

Algoritmy na stranách 26 a 27.

Lokalizace bodu

Motivace, lichoběžníková mapa, počet vrcholů i lichoběžníků lineární podle počtu úseček, popis lichoběžníků, levý, pravý horní a dolní soused. Vyhledávací struktura D, orientovaný graf bez cyklů s lichoběžníky v listech, uzly typu x a y, předpoklady na souřadnice, algoritmus TRAPESOIDAL MAP na straně 28.