Expected time analysis for Delaunay point location (Q1882851)

The authors study the point location problem in Delaunay triangulations for data and query points uniformly distributed on the unit square. Probabilistic results are presented that support and explain the simulations reported in a previous paper of the authors [Fast Delaunay point locaion with search structures, in: Eleventh Canadian Conference on Computational Geometry. 15--18 August 1999, Vancouver, Canada (1999)]. The expected point location complexities are proved to be \(O(\sqrt{n})\) for rectilinear search (which settles a conjecture of \textit{P. J. Green} and \textit{R. Sibson} [Computer J. 21, 168--173 (1978; Zbl 0377.52001)]), \(O(n^{1/3})\) for jump and walk, \(O(n^{1/4})\) for binary search and walk, \(O(n^{0.056})\) for search based on a random 2-d tree, and \(O(\log n)\) for search based on a 2-d median tree.