Mikami-Tabuchi Line Search
The idea
Grid methods pay for the routing plane cell by cell; in 1968 that memory was the binding constraint. Mikami and Tabuchi's router stores line segments instead. Level 0: through each pin, draw the maximal free horizontal and vertical lines. Level i + 1: from every point of every level-i line, draw the perpendicular free lines, each recording its parent. Two families grow, one rooted at each pin. When a line from the source family intersects a line from the target family, a route exists: follow parent pointers from the crossing back to both pins. Memory is proportional to the number of segments; on the scenario below, the level-0 state is 4 segments where Lee would store 138 cell labels.
The recipe
Step 1 (level-0 trial lines). Through the source, draw the maximal free horizontal and vertical line segments; do the same through the target. These four lines are level 0 of two families.
Step 2 (test for intersection). If any source-family line crosses any target-family line, a path exists: follow the two lines to the crossing.
Step 3 (probe and iterate). Otherwise, from every grid point on every current line, draw the maximal free perpendicular segments: these are the next level (level i + 1). Return to Step 2. Every free point of the plane is eventually covered, so a path is found whenever one exists.
Watch it work: probes until the families cross
The frames follow one search: level-0 trial lines, level-1 perpendicular probes, the first inter-family intersection, and the joined path.
Bends, length, and completeness
The crossing level determines the path's shape. Joining a level-i source line with a level-j target line produces a path with
i, jprobe levels of the two crossing lines (0 for the initial trial lines through the pins)
Because levels expand in order, the first crossing found has minimum total level, so the method minimizes bend count. Path length is not controlled: a low-bend route can be long, and no length guarantee exists. Completeness matches Lee: probing from every point of every line eventually sweeps every reachable cell, so a route is found whenever one exists.
Pros, cons, and the trade-off
Strengths
- Complete: level expansion covers every reachable cell; a route is found whenever one exists.
- Memory proportional to segments: typically orders of magnitude below cell count.
- Minimum bend count: the first crossing has minimum total level, and bends equal total level plus one.
- Bidirectional: both pins grow families, halving the effective search depth.
Weaknesses
- Not shortest: path length is uncontrolled; only bends are minimized.
- Probe growth: perpendiculars from every point of every line multiply rapidly in cluttered regions.
- No cost model: weighted edges, vias, and congestion prices have no representation on continuous segments.
- Superseded on-chip: cell grids and A* (A-star) took over once memory stopped being the constraint.
The trade-off
Mikami-Tabuchi keeps Lee's completeness while replacing the cell grid with a segment set, exchanging length optimality for minimal memory and minimal bend count. The constraint that motivated the design, memory, disappeared; grid methods absorbed its on-chip niche, and the segment representation persisted where planes are sparse.
Is it actually used today?
The evidence for Mikami-Tabuchi splits by domain: chip routing, and the adjacent territories where the line representation persists.
- Printed-circuit-board lineage: line probing powered board autorouters long after chip routers moved to grids, and escape-line reasoning persists in board-level pin-escape heuristics.
- Package and escape routing: sparse, obstacle-light planes where segment representations remain efficient.
- Teaching: the standard pairing with Hightower, which prunes the same probe scheme to a single escape point per line and loses completeness in exchange for speed.