  Let $\mathcal{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 $\gamma_i$ that the query point lies in a polygon $P_i$ of
$\mathcal{S}$. We show how to preprocess $\mathcal{S}$ such that the query time
for a point~$p\in P_i$ depends on~$\gamma_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\left(\min \left(\log n, 1 + \log
\frac{\mathrm{area}(P_i)}{\gamma_i \Delta_{p}^2}\right)\right)$, where
$\Delta_{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
$\mathcal{S}$ into convex quadrilaterals and triangles with the following
property: for any point $p\in P_i$, the quadrilateral or triangle
containing~$p$ has area $\Omega(\Delta_{p}^2)$. For the special case where
$\mathcal{S}$ is a subdivision of the unit square and
$\gamma_i=\mathrm{area}(P_i)$, we present a simpler solution that achieves a
query time of $O\left(\min \left(\log n, \log
\frac{1}{\Delta_{p}^2}\right)\right)$. The latter solution can be extended to
convex subdivisions in three dimensions.
