WikiDer > Точка Штейнера (вычислительная геометрия)

Пример точек Штейнера (выделен красным), добавленных к триангуляции для улучшения качества треугольников.

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

Название этих точек происходит от Проблема дерева Штейнера, названный в честь Якоб Штайнер, цель которого - соединить точки входа сетью минимальной общей длины. Если только входные точки используются в качестве конечных точек границ сети, то самая короткая сеть - это их минимальное остовное дерево. Однако более короткие сети часто можно получить, добавляя точки Штейнера и используя как новые точки, так и входные точки в качестве конечных точек границ.^[1]

Еще одна проблема, в которой используются точки Штейнера: Триангуляция Штейнера. Цель состоит в том, чтобы разделить входные данные (например, набор точек или многоугольник) на треугольники, пересекающиеся от края до края. В качестве вершин треугольника можно использовать как входные точки, так и точки Штейнера.^[2]

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