Devroye, L.; Mücke, E. P.; Zhu, Binhai A note on point location in Delaunay triangulations of random points. (English) Zbl 0914.68201 Algorithmica 22, No. 4, 477-482 (1998). Summary: This short note considers the problem of point location in a Delaunay triangulation of \(n\) random points, using no additional preprocessing or storage other than a standard data structure representing the triangulation. A simple and easy-to-implement (but, of course, worst-case suboptimal) heuristic is shown to take expected time \(O(n^{1/3})\). Cited in 9 Documents MSC: 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 68Q25 Analysis of algorithms and problem complexity Keywords:point location; Delaunay triangulation PDFBibTeX XMLCite \textit{L. Devroye} et al., Algorithmica 22, No. 4, 477--482 (1998; Zbl 0914.68201) Full Text: DOI