New Results on Dynamic Planar Point Location
Siu-Wing Cheng, Ravi Janardan · SIAM Journal on Computing · 1992
A point location scheme is presented for a dynamic planar subdivision whose underlying graph is only required to be connected. The operations supported include: reporting the name of the region containing a query point, inserting/deleting an edge, and inserting/deleting/moving a degree-2 vertex. The scheme uses $O(n)$ space, has a worst-case query time of $O(\log ^2 n)$, and a worst-case update time of $O(\log n)$, where n is the number of vertices currently in the subdivision. Insertion (respectively, deletion) of an arbitrary k-edge chain inside a region can be performed in $O(k\log (n + k))$ (respectively, $O(k\log n)$) time in worst-case. The scheme outperforms the solutions given in works by Fries, Mehlhorn, and Naeher and by Overmars and also handles more general subdivisions than the schemes given in works by Preparata and Tamassia. The result is based on a new solution to a dynamic visibility problem for a set of line segments in the plane that are nonintersecting, except possibly at endpoints. The scheme is then extended to speed up the insertion/deletion of a k-edge monotone chain to $O(\log ^2 n\log \log n + k)$ time (or $O(\log n\log \log n + k)$ time for an alternative model of input), but at the expense of increasing the other time bounds slightly. Additional results include a generalization to subdivisions consisting of algebraic segments of bounded degree and a persistent scheme that allows point location queries in the past and updates in the present.