Distance-sensitive point location made easy

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

Onderzoeksoutput: Bijdrage aan congresAbstractAcademic

26 Downloads (Pure)


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-2Engels
StatusGepubliceerd - 2014
Evenement30th European Workshop on Computational Geometry (EuroCG 2014) - Dead Sea, Israël
Duur: 3 mrt 20145 mrt 2014
Congresnummer: 30


Workshop30th European Workshop on Computational Geometry (EuroCG 2014)
Verkorte titelEuroCG 2014
StadDead Sea
Ander30th European Workshop on Computational Geometry
Internet adres


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

Citeer dit