A Randomized Incremental Algorithm for a Trapezoidal Map and Directed Acyclic Graph

Given a map and coordinators for a position, the planar point configuration asks to locate the position on the map. With a trapezoidal map for n line segments and a search tree of depth O(log(n)), this problem can be solved in quasi-linear time, that is in time O(n*log(n)). In order to avoid bad search trees, the input of the incremental algorithm is randomized. The lecture introduces this random incremental algorithm via examples.