A catalog of Hanan grid problems
Martin Zachariasen · Networks · 2001
Abstract We present a general rectilinear Steiner tree problem in the plane and prove that it is solvable on the Hanan grid of the input points. This result is then used to show that several variants of the ordinary rectilinear Steiner tree problem are solvable on the Hanan grid, including—but not limited to—Steiner trees for rectilinear (or isothetic) polygons, obstacle‐avoiding Steiner trees, group Steiner trees, and prize‐collecting Steiner trees. Also, the weighted region Steiner tree problem is shown to be solvable on the Hanan grid; this problem has natural applications in VLSI design routing. Finally, we give similar results for other rectilinear problems. © 2001 John Wiley & Sons, Inc.