Optimal randomized incremental construction for guaranteed logarithmic planar point location (Q340542)

The paper deals with one of the fundamental problems in computational geometry, namely with the planar point location. The authors revisit the randomized incremental construction of the trapezoidal map and the related search structures. At the beginning the authors describe the basic random incremental construction in which a trapezoidal map \(T\) is constructed and a directed acyclic graph \(G\) is maintained during the incremental construction. Moreover, some discussion on guaranteeing the logarithmic query time is made. Next, the authors study the depth \(D\) of \(G\) and the longest search path \(L\) in \(G\). They prove that the worst-case ratio between \(D\) and \(L\) can be \(\Theta(n / \log n)\), where \(n\) is the number of pairwise interior disjoint \(x\)-monotone curves inducing the planar subdivision. Later, they prove that there exists a bijection among all search paths in \(G\) and those in \(T\). Using these results the authors propose an algorithm for the construction of a trapezoidal map that has an expected \(O(n \log n)\) preprocessing time, an expected \(O(\log n)\) query time and requires an expected \(O(n)\) space.