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

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

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

Другая задача, которая использует точки Штейнера, — это триангуляция Штейнера. Цель состоит в том, чтобы разбить входные данные (например, набор точек или многоугольник) на треугольники, соединив их ребром. Как входные точки, так и точки Штейнера могут использоваться в качестве вершин треугольников. ^[2]

• Уточнение по Делоне