Red Hanan

Cuadrícula de Hanan generada para un caso de 5 terminales

En geometría , la cuadrícula de Hanan $H (S)$ de un conjunto finito $S$ de puntos en el plano se obtiene construyendo líneas verticales y horizontales a través de cada punto en $S.$

La principal motivación para estudiar la cuadrícula de Hanan surge del hecho de que se sabe que contiene un árbol de Steiner rectilíneo de longitud mínima para $S.$ ^[1] Recibe su nombre en honor a Maurice Hanan, quien fue el primero ^[2] en investigar el árbol mínimo de Steiner rectilíneo e introdujo este gráfico. ^[3]

Referencias

^ Martin Zachariasen, Un catálogo de problemas de red de Hanan , vol. 38, 2000, págs. 200-221
^ Christine R. Leverenz, Miroslaw Truszczynski, El problema del árbol de Steiner rectilíneo: algoritmos y ejemplos que utilizan permutaciones del conjunto terminal, Conferencia regional del sudeste de la ACM de 1999 , 1999, doi :10.1145/306363.306402
^ M. Hanan, Sobre el problema de Steiner con la distancia rectilínea Archivado el 4 de marzo de 2016 en Wayback Machine , J. SIAM Appl. Math. 14 (1966), 255 - 265.

[1] Martin Zachariasen, Un catálogo de problemas de red de Hanan , vol. 38, 2000, págs. 200-221

[2] Christine R. Leverenz, Miroslaw Truszczynski, El problema del árbol de Steiner rectilíneo: algoritmos y ejemplos que utilizan permutaciones del conjunto terminal, Conferencia regional del sudeste de la ACM de 1999 , 1999, doi :10.1145/306363.306402

[3] M. Hanan, Sobre el problema de Steiner con la distancia rectilínea Archivado el 4 de marzo de 2016 en Wayback Machine , J. SIAM Appl. Math. 14 (1966), 255 - 265.