Ortogonální vyhledává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. 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(nlog^d-1n), čas pro konstrukci O(nlog^d-1n) a 4as pro vyhledání O(log^dn+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. Podrobněji o jednotlivých krocích algoritmu TRAPESOIDAL MAP. Vyhledání lichoběžníku, ve kterém leží levý bod přidávané úsečky, vyhledání lichoběžníků, které jsou novou úsečkou protínány - algoritmus FOLLOW SEGMENT na straně 29. Aktualizace lichoběžníkové mapy. Aktualizace vyhledávací struktury.  (Detaily v práci O. Folvarčného.)  Odstranění předpokladů na y-nové souřadnice vrcholů úseček pomocí shear transformation a lexikografického uspořádání v uzlech typu x. Odvození očekávaného času vyhledávání O(log n), očekávané velikosti vyhledávací struktury O(n) a očekávaného času její konstrukce O(n log n).

Tabule z 9. přednášky