Сетка Ханан

Геометрическая сетка, созданная из горизонтальных и вертикальных линий, проведенных через каждую точку в наборе.

В геометрии сетка Ханана H $(S) конечного$ множества S $точек$ на плоскости получается путем построения вертикальных и горизонтальных линий, проходящих через каждую точку $S.$

Основная мотивация для изучения сетки Ханана проистекает из того факта, что она, как известно , содержит минимальное прямолинейное дерево Штейнера для $S.$ ^[1] Она названа в честь Мориса Ханана, который первым ^[2] исследовал минимальное прямолинейное дерево Штейнера и представил этот граф. ^[3]

Ссылки

^ Мартин Захариасен, Каталог проблем сетей Ханан-Грид , т. 38, 2000, стр. 200-221
^ Кристин Р. Леверенц, Мирослав Трушчинский, Задача о прямолинейном дереве Штейнера: алгоритмы и примеры с использованием перестановок терминального набора, 1999 ACM Southeast Regional Conference , 1999, doi : 10.1145/306363.306402
^ М. Ханан, О задаче Штейнера с прямолинейным расстоянием. Архивировано 4 марта 2016 г. в Wayback Machine , J. SIAM Appl. Math. 14 (1966), 255 - 265.

[1] Мартин Захариасен, Каталог проблем сетей Ханан-Грид , т. 38, 2000, стр. 200-221

[2] Кристин Р. Леверенц, Мирослав Трушчинский, Задача о прямолинейном дереве Штейнера: алгоритмы и примеры с использованием перестановок терминального набора, 1999 ACM Southeast Regional Conference , 1999, doi : 10.1145/306363.306402

[3] М. Ханан, О задаче Штейнера с прямолинейным расстоянием. Архивировано 4 марта 2016 г. в Wayback Machine , J. SIAM Appl. Math. 14 (1966), 255 - 265.