On the Rectilinear Steiner Problem
- Andreas Blass ,
- Yuri Gurevich
The Bulletin of the European Association for Theoretical Computer Science | , Vol 121
This is a gentle introduction to the Rectilinear Steiner Problem. The interest in the Rectilinear Steiner Problem is related to the Very Large-Scale Integration (VLSI) technology that combines thousands of transistors into a single chip. Our note is based on the pioneering paper of Maurice Hanan. The main result of Hanan is an algorithm reducing any solution to a solution within a so-called Hanan grid. We simplify Hanan’s algorithm.