WikiDer > Сетка Ханана - Википедия

Hanan grid - Wikipedia
Сетка Ханана, созданная для 5-контактного корпуса

В геометрия, то Сетка Hanan ЧАС(S) из конечный набор S очков в самолет получается путем построения вертикальных и горизонтальных линий через каждую точку в S.

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

Рекомендации

  1. ^ Мартин Захариасен, Каталог задач Hanan Grid Сети, т. 38, 2000, стр. 200-221.
  2. ^ Кристина Р. Леверенц, Мирослав Трущинский, Задача о прямолинейном дереве Штейнера: алгоритмы и примеры с использованием перестановок терминального множества, 1999 Юго-восточная региональная конференция ACM, 1999, Дои:10.1145/306363.306402
  3. ^ М. Ханан, О проблеме Штейнера с прямолинейным расстоянием, J. SIAM Appl. Математика. 14 (1966), 255 - 265.