×

A note on point location in Delaunay triangulations of random points. (English) Zbl 0914.68201

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})\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI