Distance-sensitive planar point location

Boris Aronov; Mark De Berg; Marcel Roeloffzen; Bettina Speckmann

doi:10.1007/978-3-642-40104-6_5

Distance-sensitive planar point location

Boris Aronov, Mark De Berg, Marcel Roeloffzen, Bettina Speckmann

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 Ω(δ _p²).

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings
Pages	49-60
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-40104-6_5
State	Published - 2013
Event	13th International Symposium on Algorithms and Data Structures, WADS 2013 - London, ON, Canada Duration: Aug 12 2013 → Aug 14 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8037 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th International Symposium on Algorithms and Data Structures, WADS 2013
Country/Territory	Canada
City	London, ON
Period	8/12/13 → 8/14/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Aronov, B., De Berg, M., Roeloffzen, M., & Speckmann, B. (2013). Distance-sensitive planar point location. In Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings (pp. 49-60). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8037 LNCS). https://doi.org/10.1007/978-3-642-40104-6_5

Distance-sensitive planar point location. / Aronov, Boris; De Berg, Mark; Roeloffzen, Marcel et al.
Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. 2013. p. 49-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8037 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aronov, B, De Berg, M, Roeloffzen, M & Speckmann, B 2013, Distance-sensitive planar point location. in Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8037 LNCS, pp. 49-60, 13th International Symposium on Algorithms and Data Structures, WADS 2013, London, ON, Canada, 8/12/13. https://doi.org/10.1007/978-3-642-40104-6_5

@inproceedings{6742bc671d1b46ab8c1b463bc01f33b9,

title = "Distance-sensitive planar point location",

abstract = "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).",

author = "Boris Aronov and {De Berg}, Mark and Marcel Roeloffzen and Bettina Speckmann",

note = "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. ; 13th International Symposium on Algorithms and Data Structures, WADS 2013 ; Conference date: 12-08-2013 Through 14-08-2013",

year = "2013",

doi = "10.1007/978-3-642-40104-6_5",

language = "English (US)",

isbn = "9783642401039",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "49--60",

booktitle = "Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings",

}

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 -

Distance-sensitive planar point location

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this