Steiner point (computational geometry)

For other uses, see Steiner point.
Example of Steiner points (in red) added to a triangulation to improve the quality of triangles.

In computational geometry, a Steiner point is a point that is not part of the input to a geometric optimization problem but is added during the solution of the problem, to create a better solution than would be possible from the original points alone.

The name of these points comes from the Steiner tree problem, named after Jakob Steiner, in which the goal is to connect the input points by a network of minimum total length. If the input points alone are used as endpoints of the network edges, then the shortest network is their minimum spanning tree. However, shorter networks can often be obtained by adding Steiner points, and using both the new points and the input points as edge endpoints.[1]

Another problem that uses Steiner points is Steiner triangulation. The goal is to partition an input (such as a point set or polygon) into triangles, meeting edge-to-edge. Both input points and Steiner points may be used as triangle vertices.[2]

  1. ^ Hwang, F. K.; Richards, D. S.; Winter, P. (1992), The Steiner Tree Problem, Annals of Discrete Mathematics, vol. 53, Elsevier, ISBN 0-444-89098-X.
  2. ^ de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), Computational Geometry: Algorithms and Applications (2nd ed.), Springer, p. 293, ISBN 9783540656203