Hoppa-och-gå-algoritm - Jump-and-Walk algorithm

Jump-and-Walk är en algoritm för punktplats i trianguleringar (även om de flesta av den teoretiska analysen utfördes i 2D- och 3D-slumpmässiga Delaunay-trianguleringar). Överraskande behöver algoritmen inte någon förbehandling eller komplexa datastrukturer förutom någon enkel representation av själva trianguleringen. Föregångaren till Jump-and-Walk berodde på Lawson (1977) och Green and Sibson (1978), som väljer en slumpmässig utgångspunkt S och sedan går från S mot frågefunkten Q en triangel i taget. Men ingen teoretisk analys var känd för dessa föregångare förrän efter mitten av 1990-talet.

Jump-and-Walk väljer en liten grupp provpunkter och startar promenad från provpunkten som är närmast Q tills simplexet som innehåller Q finns. Algoritmen var en folklore i praktiken under en tid, och den formella presentationen av algoritmen och analysen av dess prestanda på 2D slumpmässig Delaunay-triangulering gjordes av Devroye, Mucke och Zhu i mitten av 1990-talet (uppsatsen publicerades i Algorithmica, 1998) . Analysen på slumpmässig 3D-Delaunay-triangulering gjordes av Mucke, Saias och Zhu (ACM Symposium of Computational Geometry, 1996). I båda fallen antogs ett gränsvillkor, nämligen, Q måste vara något borta från gränsen för det konvexa domänet där topparna i den slumpmässiga Delaunay-trianguleringen dras. 2004 visade Devroye, Lemaire och Moreau att i 2D kan gränstillståndet dras tillbaka (uppsatsen visas i Computational Geometry: Theory and Applications, 2004).

Jump-and-Walk har använts i många kända mjukvarupaket, t.ex. QHULL, Triangle och CGAL.

referenser

  • Green, PJ; 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 ytinterpolation", i Rice, JR , Mathematical Software III , NY: Academic Press, s. 161–194.
  • Devroye, Luc; Lemaire, Christophe; Moreau, Jean-Michel (2004), "Förväntad tidsanalys för Delaunay-punktplats", Computational Geometry: Theory and Applications , 29 (2): 61–89, doi : 10.1016 / j.comgeo.2004.02.002 , MR  2082208.
  • Devroye, L .; Mücke, EP; Zhu, Binhai (1998), "En notering om att punktens läge i Delaunay triangulations av slumpmässiga punkter", Algorithmica , 22 (4): 477-482, CiteSeerX  10.1.1.15.8612 , doi : 10,1007 / PL00009234 , MR  1.701.623.
  • Mücke, Ernst P .; Saias, Isaac; Zhu, Binhai (1999), "Snabb randomiserad punktplats utan förbehandling i två- och tredimensionella Delaunay-trianguleringar", Specialutgåva för 12: e ACM- symposium om beräkningsgeometri (Philadelphia, PA, 1996), Computational Geometry: Theory and Applications , 12 (1–2): 63–83, doi : 10.1016 / S0925-7721 (98) 00035-2 , MR  1677599.