TY - GEN

T1 - Distance-sensitive planar point location

AU - Aronov, Boris

AU - De Berg, Mark

AU - Roeloffzen, Marcel

AU - Speckmann, Bettina

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

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 -