TY - GEN

T1 - Distance-sensitive planar point location

AU - Aronov, Boris

AU - De Berg, Mark

AU - Roeloffzen, Marcel

AU - Speckmann, Bettina

N1 - Funding Information:
B. Aronov has been supported by United States–Israel Binational Science Foundation grant 2006/194 , by NSF Grants CCF-08-30691 , CCF-11-17336 , and CCF-12-18791 , and by NSA MSP Grant H98230-10-1-0210 . D. Eppstein has been supported by NSF grant 1217322 and ONR grant N00014-08-1-1015 . M. Roeloffzen and B. Speckmann were supported by the Netherlands' Organisation for Scientific Research ( NWO ) under project nos. 600.065.120 and 639.023.208 , respectively.

PY - 2013

Y1 - 2013

N2 - Let S be a connected planar polygonal subdivision with n edges and of total area 1. 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 1/Δp, log n)), 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 Ω(δ p2).

AB - Let S be a connected planar polygonal subdivision with n edges and of total area 1. 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 1/Δp, log n)), 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 Ω(δ p2).

UR - http://www.scopus.com/inward/record.url?scp=84881161555&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84881161555&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40104-6_5

DO - 10.1007/978-3-642-40104-6_5

M3 - Conference contribution

AN - SCOPUS:84881161555

SN - 9783642401039

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 49

EP - 60

BT - Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings

T2 - 13th International Symposium on Algorithms and Data Structures, WADS 2013

Y2 - 12 August 2013 through 14 August 2013

ER -