Proximate planar point location
John Iacono, Stefan Langerman · 2003
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=q1, qm, the structure presented executes qi in time O(log d(qi-1,qi)). 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 qi-1 to qi. The data structure uses O(n log log n) space.