Lokalizace bodu

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