proximate planar point location
A new data structure is presented for planar point location that executes a point location query quickly if it is spatially near the previous query. Given a triangulation T of size n and a sequence of point location queries A=q 1 , q m , the structure presented executes q i in time O(log d(q i-1 ,q i )) . The distance function, d , that is used is a two dimensional generalization of rank distance that counts the number of triangles in a region from q i-1 to q i . The data structure uses O(n log log n) space.
planar point location