Jump-and-Walk Algorithm

Jump-and-Walk is an algorithm for point location in triangulations that, unlike many alternatives, needs no preprocessing or complex data structures beyond a simple representation of the triangulation itself. It builds on earlier work by Lawson in 1977 and by Green and Sibson in 1978, which used a random starting point and moved iteratively through adjacent triangles toward the target location, though rigorous theoretical analysis of the running time of this approach did not appear until the mid-1990s and later.