Line-Probing / Line-Search

Line-probing algorithms search for routes directly based on the geometry. Unlike maze-routers, line-probing does not necessarily need a grid. Hence they can be more memory efficient and faster.

Example algorithms in the literature are:

  • Hightower's algorithm
  • Mikami-Tabuchi algorithm

The above algorithms do not guarantee finding the shortest path between two terminals.

Example implementations in LibrEDA

  • mycelium-router contains an experimental detail router based on a line-search algorithm which guarantees finding the shortest path between two nodes if one exists.