Fast delaunay point location with search structures.
Luc Devroye, Christophe Lemaire, Jean-Michel Moreau · Canadian Conference on Computational Geometry · 1999
We study the expected time behaviour of the Jumpand-walk paradigm when the set of sites is controlled by a binary search tree or a well-balanced 2-d tree. Throughout the paper, we shall assume that we are given a Delaunay triangulation on N sites uniformly distributed in the unit 2-dimensional square, [0; 1]. We are requested to locate a query point q, which will be assumed to be bounded away from the boundary of the Delaunay triangulation, as the expected analysis of the general case calls for more powerful tools (to be published in a future paper).