Dynamization of the Trapezoid Method for Planar Point Location in MonotoneSubdivisions

摘要

We present a fully dynamic data structure for point location in a monotonesubdivision, based on the trapezoid method. The operations supported are insertion and deletion of vertices and edges, and horizontal translation of vertices. Let n be the current number of vertices of the subdivision. Point location queries take O(log(n)) time, while updates take O(log 2 (n)) time (amortized for vertex insertion/deletion and worst-case for the other updates). The space requirement is O ((n) log (n)). This is the first fully dynamic point location data structure for monotone subdivisions that achieves optimal query time.... Computational geometry, Planar point location, Dynamic data structure, Monotone subdivision, Analysis of algorithms.