Expected time analysis for Delaunay point location

DOI10.1016/J.COMGEO.2004.02.002MaRDI QIDQ1882851zbMATH OpenOpenAlexDBLPWikidataFDO

Authors C. Lemaire, J.-M. Moreau, Luc Devroye

Publication date 1 October 2004

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2004.02.002

computational geometry Delaunay triangulation point location probabilistic analysis random tree Voronoi diagram

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Review text

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.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Expected time analysis for Delaunay point location

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1882851)