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:

@article{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"
,journal=	"Computational Geometry: Theory and Applications"
,volume=	12
,number=	""
,year=		1999
,pages=		"63--83"
,url="ftp://ftp.cfar.umd.edu/TRs/CVL-Reports-1996/TR3621-Mucke.ps.gz"
}