Fully Dynamic Point Location in a Monotone Subdivision
Franco P. Preparata, Roberto Tamassia · SIAM Journal on Computing · 1989
In this paper a dynamic technique for locating a point in a monotone planar subdivision, whose current number of vertices is n, is presented. The (complete set of) update operations are insertion of a point on an edge and of a chain of edges between two vertices, and their reverse operations. The data structure uses space $O(n)$. The query time is $O(\log ^2 n)$, the time for insertion/deletion of a point is $O(\log n)$, and the time for insertion/deletion of a chain with k edges is $O(\log ^2 n + k)$, all worst-case. The technique is conceptually a special case of the chain method of Lee and Preparata and uses the same query algorithm. The emergence of full dynamic capabilities is afforded by a subtle choice of the chain set (separators), which induces a total order on the set of regions of the planar subdivision.