Tech Report CS-89-24

Dynamic Planar Point Location with Optimal Query Time

Roberto Tamassia and Franco P. Preparata

March 1989

Abstract:

We present a new dynamic technique for locating a point in a convex planar subdivision whose {\em n} vertices lie on a fixed set of {\em N} horizontal lines. The supported update operations are insertion/deletion of vertices and edges and (horizontal) translation of vertices. Our method achieves query time $O(\log n + \log N)$, space $O(N + n \log N)$, and insertion/deletion time $O(\log n \log N)$. Hence, for $N = O(n)$, the query time is $O(\log n)$, which is optimal. The proposed technique, based on the {\em trapezoid method}, provides an efficient solution to many significant applications where the most frequent operation is the point location query, while updates are more rarely executed.

(complete text in pdf)