A fundamental problem in computer science is that of finding a path in a graph. When the whole graph is available, standard pathfinding algorithms can be applied such as Depth-First Search or Dijkstra's Algorithm. However, the problem of finding a path is more challenging in an online setting when at every step of the computation, only local information is available to the routing algorithm (such as the neighbourhood of the current vertex in the path). The difficulty is in deciding which edge to follow with only this local information.
We will explore different techniques for finding a path in a graph in the online setting with an emphasis on finding paths in geometric graphs (graphs whose vertices are points in the plane and whose edges are segments between these points). We will highlight the difficulties involved with routing in this setting and review some of the currently best-known routing algorithms in this setting.