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

Blackboards