Dynamization of the trapezoid method for planar point location (extended abstract)
Yi‐Jen Chiang, Roberto Tamassia · 1991
We present a fully dynamic data structure for point location in a monotone subdivision, 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 0(log2 n) time.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.