В вычислительной геометрии , точка Штейнера является точкой , которая не является частью вклада в геометрическую задачу оптимизации , но добавляют при решении задачи, чтобы создать лучшее решение , чем было бы возможно только из исходных точек.
Название этих точек происходит от проблемы дерева Штайнера , названной в честь Якоба Штайнера , в которой цель состоит в том, чтобы соединить входные точки сетью минимальной общей длины. Если только входные точки используются в качестве конечных точек границ сети, то самая короткая сеть является их минимальным остовным деревом . Однако более короткие сети часто можно получить, добавляя точки Штейнера и используя как новые точки, так и входные точки в качестве конечных точек ребер. [1]
Еще одна проблема, в которой используются точки Штейнера, - это триангуляция Штейнера . Цель состоит в том, чтобы разделить входные данные (например, набор точек или многоугольник) на треугольники, пересекающиеся от края до края. В качестве вершин треугольника можно использовать как входные точки, так и точки Штейнера. [2]
Ссылки [ править ]
- ^ Hwang, FK; Ричардс, Д.С. Уинтер, П. (1992), Проблема дерева Штейнера , Анналы дискретной математики, 53 , Elsevier , ISBN 0-444-89098-X.
- ^ де Берг, Марк; ван Кревельд, Марк; Овермарс, Марк; Шварцкопф, Отфрид (2000), Вычислительная геометрия: алгоритмы и приложения (2-е изд.), Springer, стр. 293, ISBN 9783540656203
