computer science

Jump-and-Walk algorithm

Jump-and-Walk algorithm is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Jump-and-Walk algorithm rather than just read about it. In short: 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.

Key takeaways

Jump-and-Walk algorithm belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Jump-and-Walk algorithm to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Jump-and-Walk algorithm from memory before moving on to harder problems.

Reference excerpt

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 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, CiteSeerX 10.1.1.15.8612, doi:10.1007/PL00009234, MR 1701623, S2CID 3000041 {{citation}}: Cite uses deprecated parameter |citeseerx= (help). 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.

Worked examples

Example 1 — a first encounter with Jump-and-Walk algorithm

Start with the simplest possible case. Write down what Jump-and-Walk algorithm claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Jump-and-Walk algorithm before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Jump-and-Walk algorithm ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Jump-and-Walk algorithm

In research: Jump-and-Walk algorithm appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Jump-and-Walk algorithm in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Jump-and-Walk algorithm is common in secondary-school and first-year university syllabi. It links to neighbouring topics Algorithms, Triangulation (geometry), so understanding it makes those chapters shorter.
In everyday life: Look for Jump-and-Walk algorithm outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Jump-and-Walk algorithm” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Jump-and-Walk algorithm in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Jump-and-Walk algorithm means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Jump-and-Walk algorithm out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Jump-and-Walk algorithm in simple terms?

Why does Jump-and-Walk algorithm matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Jump-and-Walk algorithm?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Jump-and-Walk algorithm.