Let be a connected planar polygonal subdivision with n edges and of total area 1. We present a data structure for point location in TeX 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 TeX, where ¿p is the distance of the query point p to the boundary of the region containing p. Our structure is based on the following result: any simple polygon P can be decomposed into a linear number of convex quadrilaterals with the following property: for any point p¿¿¿P, the quadrilateral containing p has area TeX.
|Title of host publication||Algorithms and Data Structures (13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings)|
|Editors||F. Dehne, R. Solis-Orba, J.-R. Sack|
|Place of Publication||Berlin|
|Publication status||Published - 2013|
|Name||Lecture Notes in Computer Science|