Cuadrícula de Hanan

La red de Hanan de un conjunto finito de puntos en el plano se obtiene dibujando líneas verticales y horizontales a través de cada punto del conjunto.

La principal razón para estudiar la red de Hanan se debe al hecho de que ciertamente contiene un árbol de Steiner rectangular para S [1] . La red lleva el nombre de M. Hanan, quien primero [2] exploró el árbol mínimo rectangular de Steiner e introdujo este gráfico [3] .

Notas

1. ↑ Martín Zachariasen. Un catálogo de problemas de cuadrícula de Hanan  // Redes. - 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 Conferencia Regional Sudeste , 1999, doi : 10.1145/306363.306402
3. ↑ M. Hanan. Sobre el problema de Steiner con la distancia rectilínea  // J. SIAM Appl. Matemáticas. - 1966. - Nº 14 . - S. 255-265 .