We show that the memoryless routing algorithms Greedy Walk, Compass Walk,and all variants of visibility walk based on orientation predicates are asymptotically optimalin the average case on the Delaunay triangulation. Morespecifically, we consider the Delaunay triangulation of an unbounded Poisson pointprocess of unit rate and demonstrate that the worst-case path between any twovertices inside a domain of area $n$ has a number of steps that is not asymptotically morethan the shortest path which exists between those two vertices with probabilityconverging to one (as long as the vertices are sufficiently far apart.) As acorollary, it follows that the worst-case path has $O(\sqrt{n}\,)$ steps in thelimiting case, under the same conditions. Our results have applications inrouting in mobile networks and also settle a long-standing conjecture in pointlocation using walking algorithms. Our proofs use techniques frompercolation theory and stochastic geometry.