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