Grid of Hanan

Hanan-gittret för en ändlig uppsättning punkter i planet erhålls genom att dra vertikala och horisontella linjer genom varje punkt i uppsättningen.

Det främsta skälet till att studera Hanan-gittret beror på att det förvisso innehåller ett rektangulärt Steinerträd för S [1] . Gallret är uppkallat efter M. Hanan, som först [2] utforskade Steiners rektangulära minimalträd och introducerade denna graf [3] .

Anteckningar

1. ↑ Martin Zachariasen. En katalog över Hanan Grid-problem  // Nätverk. - 2000. - T. 38 . - S. 200-221 .
2. ↑ Christine R. Leverenz, Miroslaw Truszczynski, The Rectilinear Steiner Tree Problem: Algoritms and Examples using Permutations of the Terminal Set , 1999 ACM Southeast Regional Conference , 1999, doi : 10.1145/306363.306402
3. ↑ M. Hanan. Om Steiners problem med rätlinjigt avstånd  // J. SIAM Appl. Matematik. - 1966. - Nr 14 . - S. 255-265 .