Distance-sensitive point location made easy

Let S be a planar polygonal subdivision with n edges contained in the unit square. We present a data structure for point location in S where queries with points far away from any region boundary are answered faster. More precisely, we show that point location queries can be answered in time O(1 + min(log \frac{1}{\Delta_p} , log n)), where {\Delta_p} is the Euclidean distance of the query point p to the boundary of the region containing p. Our solution consists of a depth-bounded quadtree and a general point location structure, both of which can be constructed in O(n log n)time. We also show how to extend the result to convex polyhedral subdivisions in three dimensions.