Distance-Sensitive Planar Point Location

Boris Aronov, Mark de Berg, David Eppstein +2

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$ tha…