# Distance-sensitive point location made easy

B. Aronov, M.T. Berg, de, D. Eppstein, M.J.M. Roeloffzen, B. Speckmann

## Samenvatting

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.
Originele taal-2 Engels 1-4 Gepubliceerd - 2014 30th European Workshop on Computational Geometry (EuroCG 2014) - Dead Sea, IsraëlDuur: 3 mrt 2014 → 5 mrt 2014Congresnummer: 30https://www.cs.bgu.ac.il/~eurocg14/

### Workshop

Workshop 30th European Workshop on Computational Geometry (EuroCG 2014) EuroCG 2014 Israël Dead Sea 3/03/14 → 5/03/14 30th European Workshop on Computational Geometry https://www.cs.bgu.ac.il/~eurocg14/

## Vingerafdruk

Duik in de onderzoeksthema's van 'Distance-sensitive point location made easy'. Samen vormen ze een unieke vingerafdruk.