Point Location in Well-Shaped Meshes Using Jump-and-Walk
Jean-Lou De Carufel, Craig Dillabaugh, Anil Maheshwari · Canadian Conference on Computational Geometry · 2011
We present results on executing point location queries in well-shaped meshes in R 2 and R 3 using the Jumpand-Walk paradigm. If the jump step is performed on a nearest-neighbour search structure built on the vertices of the mesh, we demonstrate that the walk step can be performed in guaranteed constant time. Constant time for the walk step holds even if the jump step starts with an approximate nearest neighbour.