Abstract. 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.

Postscript [77k] of the UMD College Park CVL/CfAR 1996 Techreport

Suggested BIBTeX entry:

@inproceedings{LABEL
,author=        "M{\"u}cke, E. P. and Saias, I. and Zhu, B."
,title=         "Fast Randomized Point Location Without Preprocessing
                in Two- and Three-dimensional Delaunay Triangulations"
,booktitle=     "Proceedings of the 11th Annual Symposium on
                Computational Geometry"
,year=          1996
,pages=         "274--283"
,note=		"To appear in
		{\em Computational Geometry: Theory and Applications}"
,url=           "ftp://ftp.cfar.umd.edu/TRs/CVL-Reports-1996/TR3621-Mucke.ps.gz"
}