Algoritmo de salto y caminata

Jump-and-Walk es un algoritmo para la localización de puntos en triangulaciones (aunque la mayor parte del análisis teórico se realizó en triangulaciones de Delaunay aleatorias en 2D y 3D ). Sorprendentemente, el algoritmo no requiere ningún preprocesamiento ni estructuras de datos complejas, salvo una representación simple de la triangulación. El predecesor de Jump-and-Walk fue desarrollado por Lawson (1977) y Green y Sibson (1978), quienes seleccionan un punto de partida aleatorio S y luego se desplazan desde S hacia el punto de consulta Q, triángulo a triángulo. Sin embargo, no se conocía ningún análisis teórico de estos predecesores hasta mediados de la década de 1990.

El algoritmo Jump-and-Walk selecciona un pequeño grupo de puntos de muestra y comienza el recorrido desde el punto de muestra más cercano a Q hasta encontrar el simplex que contiene a Q. Este algoritmo fue de uso común durante un tiempo, y la presentación formal del mismo y el análisis de su rendimiento en la triangulación aleatoria de Delaunay en 2D fueron realizados por Devroye, Mucke y Zhu a mediados de la década de 1990 (el artículo se publicó en Algorithmica, 1998). El análisis en la triangulación aleatoria de Delaunay en 3D fue realizado por Mucke, Saias y Zhu (ACM Symposium of Computational Geometry, 1996). En ambos casos, se asumió una condición de contorno : Q debe estar ligeramente alejado del límite del dominio convexo donde se trazan los vértices de la triangulación aleatoria de Delaunay. En 2004, Devroye, Lemaire y Moreau demostraron que en 2D se puede prescindir de la condición de contorno (el artículo apareció en Computational Geometry: Theory and Applications, 2004).

El método Jump-and-Walk se ha utilizado en muchos paquetes de software famosos, por ejemplo, QHULL, Triangle y CGAL .

• Green, PJ; Sibson, R. (1978), "Cálculo de teselaciones de Dirichlet en el plano", The Computer Journal , 21 (2): 168– 173, doi : 10.1093/comjnl/21.2.168 , MR 0485467 .
• Lawson, C. (1977), "Software para interpolación de superficies C1", en Rice, JR (ed.), Mathematical Software III , NY: Academic Press, pp . 161–194 .
• Devroye, Luc; Lemaire, Christophe; Moreau, Jean-Michel (2004), "Análisis del tiempo esperado para la localización de puntos de Delaunay", Geometría Computacional: Teoría y Aplicaciones , 29 (2): 61– 89, doi : 10.1016/j.comgeo.2004.02.002 , MR 2082208 .
• Devroye, L.; Mücke, EP; Zhu, Binhai (1998), "Una nota sobre la localización de puntos en triangulaciones de Delaunay de puntos aleatorios", Algorithmica , 22 (4): 477– 482, CiteSeerX 10.1.1.15.8612 , doi : 10.1007/PL00009234 , MR 1701623 , S2CID 3000041   .
• Mücke, Ernst P.; Saias, Isaac; Zhu, Binhai (1999), "Localización rápida de puntos aleatorios sin preprocesamiento en triangulaciones de Delaunay bidimensionales y tridimensionales", Número especial para el 12.º Simposio ACM sobre Geometría Computacional (Filadelfia, PA, 1996), Geometría Computacional: Teoría y Aplicaciones , 12 ( 1–2 ): 63–83 , doi : 10.1016/S0925-7721(98)00035-2 , MR 1677599 .