Distance-sensitive planar point location

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

    Research output: Contribution to journalArticlepeer-review


    Let S be a connected planar polygonal subdivision with n edges that we want to preprocess for point-location queries, and where we are given the probability γi that the query point lies in a polygon Pi of S. We show how to preprocess S such that the query time for a point p∈Pi depends on γi and, in addition, on the distance from p to the boundary of Pi - the further away from the boundary, the faster the query. More precisely, we show that a point-location query can be answered in time O(min (logn, 1+log area(Pi)/γiΔp2)), where Δp is the shortest Euclidean distance of the query point p to the boundary of Pi. Our structure uses O(n) space and O(nlogn) preprocessing time. It is based on a decomposition of the regions of S into convex quadrilaterals and triangles with the following property: for any point p ∈ Pi, the quadrilateral or triangle containing p has area Ω(Δp2). For the special case where S is a subdivision of the unit square and γi=area(Pi), we present a simpler solution that achieves a query time of O(min(logn,log 1/Δp2)). The latter solution can be extended to convex subdivisions in three dimensions.

    Original languageEnglish (US)
    Pages (from-to)17-31
    Number of pages15
    JournalComputational Geometry: Theory and Applications
    StatePublished - Apr 1 2016


    • Mesh generation
    • Point location
    • Quadtree

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics


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

    Cite this