Point location in spatial subdivision is one of the most studied problems in computational geometry. In the case of triangulations of ℝd, we revisit the problem to exploit a possible coherence between the query-points. For a single query, walking in the triangulation is a classical strategy with good practical behavior and expected complexity O(n1/d) if the points are evenly distributed. For a batch of query-points, the main idea is to use previous queries to improve the current one; we compare various strategies that have an influence on the constant hidden in the big-O notation. Still regarding the complexity of a query, we show how the Delaunay hierarchy can be used to answer, under some hypotheses, a query q with a O(log#(pq) ) randomized expected complexity, where #(.) indicates the number of simplices crossed by the line pq, and p is a previously located query. The data structure has O(n logn) construction complexity and O(n) memory complexity.
This document was translated from LATEX by HEVEA.