Distance-Sensitive Planar Point Location

Original · EN

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 γᵢ that the query point lies in a polygon Pᵢ of S. We show how to preprocess S such that the query time for a point p∈ Pᵢ depends on γᵢ and, in addition, on the distance from p to the boundary of Pᵢ---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((n, 1 + area(Pᵢ)γᵢ Δₚ²)), where Δₚ is the shortest Euclidean distance of the query point p to the boundary of Pᵢ. Our structure uses O(n) space and O(n 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ᵢ, the quadrilateral or triangle containing p has area Ω(Δₚ²). For the special case where S is a subdivision of the unit square and γᵢ=area(Pᵢ), we present a simpler solution that achieves a query time of O((n, 1Δₚ²)). The latter solution can be extended to convex subdivisions in three dimensions.