Let S be a connected planar polygonal subdivision with n edges that we want to preprocess for point-location queries, and where we are given the probability γ i that the query point lies in a polygon P i of S . We show how to preprocess S such that the query time for a point p ? P i depends on γ i and, in addition, on the distance from p to the boundary of P i -the further away from the boundary, the faster the query. More precisely, we show that a point-location query can be answered in time O ( min ? ( log ? n , 1 + log ? area ( P i ) γ i Δ p 2 ) ) , where Δ p is the shortest Euclidean distance of the query point p to the boundary of P i . Our structure uses O ( n ) space and O ( n log ? n ) preprocessing time. It is based on a decomposition of the regions of S into convex quadrilaterals and triangles with the following property: for any point p ? P i , the quadrilateral or triangle containing p has area ? ( Δ p 2 ) . For the special case where S is a subdivision of the unit square and γ i = area ( P i ) , we present a simpler solution that achieves a query time of O ( min ? ( log ? n , log ? 1 Δ p 2 ) ) . The latter solution can be extended to convex subdivisions in three dimensions.
['Boris Aronov', 'Mark de Berg', 'David Eppstein', 'Marcel Roeloffzen', 'Bettina Speckmann']
Distance-sensitive planar point location