Distance-sensitive planar point location

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)


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.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures (13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings)
EditorsF. Dehne, R. Solis-Orba, J.-R. Sack
Place of PublicationBerlin
ISBN (Print)978-3-642-40103-9
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Distance-sensitive planar point location'. Together they form a unique fingerprint.

Cite this