Grid of Hanan

Hanan-gitteret af et begrænset sæt punkter i planet opnås ved at tegne lodrette og vandrette linjer gennem hvert punkt i sættet.

Hovedårsagen til at studere Hanan-gitteret skyldes, at det bestemt indeholder et rektangulært Steiner-træ for S [1] . Gitteret er opkaldt efter M. Hanan, som først [2] udforskede Steiner rektangulære minimaltræ og introducerede denne graf [3] .

Noter

1. ↑ Martin Zachariasen. Et katalog over Hanan Grid Problemer  // Netværk. - 2000. - T. 38 . - S. 200-221 .
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. ↑ M. Hanan. Om Steiners problem med retlinet afstand  // J. SIAM Appl. Matematik. - 1966. - Nr. 14 . - S. 255-265 .