Jump-and-Walk is an algorithm for point location in triangulations (though most of the theoretical analysis were performed in 2D and 3D random Delaunay triangulations). Surprisingly, the algorithm does not need any preprocessing or complex data structures except some simple representation of the triangulation itself. The predecessor of Jump-and-Walk was due to Lawson (1977) and Green and Sibson (1978), which picks a random starting point S and then walks from S toward the query point Q one triangle at a time. But no theoretical analysis was known for these predecessors until after mid-1990s.
Jump-and-Walk picks a small group of sample points and starts the walk from the sample point which is the closest to Q until the simplex containing Q is found. The algorithm was a folklore in practice for some time, and the formal presentation of the algorithm and the analysis of its performance on 2D random Delaunay triangulation was done by Devroye, Mucke and Zhu in mid-1990s (the paper appeared in Algorithmica, 1998). The analysis on 3D random Delaunay triangulation was done by Mucke, Saias and Zhu (ACM Symposium of Computational Geometry, 1996). In both cases, a boundary condition was assumed, namely, Q must be slightly away from the boundary of the convex domain where the vertices of the random Delaunay triangulation are drawn. In 2004, Devroye, Lemaire and Moreau showed that in 2D the boundary condition can be withdrawn (the paper appeared in Computational Geometry: Theory and Applications, 2004).
Jump-and-Walk has been used in many famous software packages, e.g., QHULL, Triangle and CGAL.
Referencesedit
Green, P. J.; Sibson, R. (1978), "Computing Dirichlet tessellations in the plane", The Computer Journal, 21 (2): 168–173, doi:10.1093/comjnl/21.2.168, MR 0485467.
Lawson, C. (1977), "Software for C1 surface interpolation", in Rice, J. R. (ed.), Mathematical Software III, NY: Academic Press, pp. 161–194.
Devroye, Luc; Lemaire, Christophe; Moreau, Jean-Michel (2004), "Expected time analysis for Delaunay point location", Computational Geometry: Theory and Applications, 29 (2): 61–89, doi:10.1016/j.comgeo.2004.02.002, MR 2082208.
Devroye, L.; Mücke, E. P.; Zhu, Binhai (1998), "A note on point location in Delaunay triangulations of random points", Algorithmica, 22 (4): 477–482, CiteSeerX10.1.1.15.8612, doi:10.1007/PL00009234, MR 1701623, S2CID 3000041.
Mücke, Ernst P.; Saias, Isaac; Zhu, Binhai (1999), "Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations", Special issue for 12th ACM Symposium on Computational Geometry (Philadelphia, PA, 1996), Computational Geometry: Theory and Applications, 12 (1–2): 63–83, doi:10.1016/S0925-7721(98)00035-2, MR 1677599.
May 05, 2024
jump, walk, algorithm, jump, walk, algorithm, point, location, triangulations, though, most, theoretical, analysis, were, performed, random, delaunay, triangulations, surprisingly, algorithm, does, need, preprocessing, complex, data, structures, except, some, . Jump and Walk is an algorithm for point location in triangulations though most of the theoretical analysis were performed in 2D and 3D random Delaunay triangulations Surprisingly the algorithm does not need any preprocessing or complex data structures except some simple representation of the triangulation itself The predecessor of Jump and Walk was due to Lawson 1977 and Green and Sibson 1978 which picks a random starting point S and then walks from S toward the query point Q one triangle at a time But no theoretical analysis was known for these predecessors until after mid 1990s Jump and Walk picks a small group of sample points and starts the walk from the sample point which is the closest to Q until the simplex containing Q is found The algorithm was a folklore in practice for some time and the formal presentation of the algorithm and the analysis of its performance on 2D random Delaunay triangulation was done by Devroye Mucke and Zhu in mid 1990s the paper appeared in Algorithmica 1998 The analysis on 3D random Delaunay triangulation was done by Mucke Saias and Zhu ACM Symposium of Computational Geometry 1996 In both cases a boundary condition was assumed namely Q must be slightly away from the boundary of the convex domain where the vertices of the random Delaunay triangulation are drawn In 2004 Devroye Lemaire and Moreau showed that in 2D the boundary condition can be withdrawn the paper appeared in Computational Geometry Theory and Applications 2004 Jump and Walk has been used in many famous software packages e g QHULL Triangle and CGAL References editGreen P J Sibson R 1978 Computing Dirichlet tessellations in the plane The Computer Journal 21 2 168 173 doi 10 1093 comjnl 21 2 168 MR 0485467 Lawson C 1977 Software for C1 surface interpolation in Rice J R ed Mathematical Software III NY Academic Press pp 161 194 Devroye Luc Lemaire Christophe Moreau Jean Michel 2004 Expected time analysis for Delaunay point location Computational Geometry Theory and Applications 29 2 61 89 doi 10 1016 j comgeo 2004 02 002 MR 2082208 Devroye L Mucke E P Zhu Binhai 1998 A note on point location in Delaunay triangulations of random points Algorithmica 22 4 477 482 CiteSeerX 10 1 1 15 8612 doi 10 1007 PL00009234 MR 1701623 S2CID 3000041 Mucke Ernst P Saias Isaac Zhu Binhai 1999 Fast randomized point location without preprocessing in two and three dimensional Delaunay triangulations Special issue for 12th ACM Symposium on Computational Geometry Philadelphia PA 1996 Computational Geometry Theory and Applications 12 1 2 63 83 doi 10 1016 S0925 7721 98 00035 2 MR 1677599 Retrieved from https en wikipedia org w index php title Jump and Walk algorithm amp oldid 1171004870, wikipedia, wiki, book, books, library,
