Fast Randomized Point Location without Preprocessing in Two- and Three-Dimensional Delaunay Triangulations

This paper studies the point location problem in Delaunay triangulations without preprocessing and additional storage. The proposed procedure finds the query point simply by "walking through" the triangulation, after selecting a "good starting point" by random sampling. The analysis generalizes and extends a recent result for d = 2 dimensions by proving this procedure to take expected time close to O(n^(1/(d+1))) for point location in Delaunay triangulations of n random points in d = 3 dimensions. Empirical results in both two and three dimensions show that this procedure is efficient in practice