Adaptive Planar Point Location

Siu-Wing Cheng, Man-Kit Lau

We present self-adjusting data structures for answering point location queries in convex and connected subdivisions. Let $n$ be the number of vertices in a convex or connected subd…