We present results on executing point location queries in well-shaped meshes in R2 and R3 using the Jump- And-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.

Additional Metadata
Conference 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
Citation
De Carufel, J.-L. (Jean-Lou), Dillabaugh, C. (Craig), & Maheshwari, A. (2011). Point location in well-shaped meshes using jump-and-walk. Presented at the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011.