Tech Report CS-92-06

Dynamization of the Trapezoid Method for Planar Point Location in Monotone Subdivisions

Yi-Jen Chiang and Roberto Tamassia

January 1992


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 $O(\log^2 n)$ time (amortized for vertex insertion/deletion and worst-case for the others). 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.

(complete text in pdf or gzipped postscript)