Hanan_grid

Hanan grid

Hanan grid

Geometric grid created from horizontal and vertical lines drawn through each point in a set

In geometry, the Hanan grid H(S) of a finite set S of points in the plane is obtained by constructing vertical and horizontal lines through each point in S.

Hanan grid generated for a 5-terminal case

The main motivation for studying the Hanan grid stems from the fact that it is known to contain a minimum length rectilinear Steiner tree for S.[1] It is named after Maurice Hanan, who was first[2] to investigate the rectilinear Steiner minimum tree and introduced this graph.[3]

References

  1. [1]
    Martin Zachariasen, A Catalog of Hanan Grid Problems Networks, vol. 38, 2000, pp. 200-221
  2. [2]
    Christine R. Leverenz, Miroslaw Truszczynski, The Rectilinear Steiner Tree Problem: Algorithms and Examples using Permutations of the Terminal Set, 1999 ACM Southeast Regional Conference, 1999, doi:10.1145/306363.306402
  3. [3]
    M. Hanan, On Steiner's problem with rectilinear distance, J. SIAM Appl. Math. 14 (1966), 255 - 265.
Share this article:

This article uses material from the Wikipedia article Hanan_grid, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.