Steiner point (computational geometry)

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 wouldn't be possible from the original points alone.

Example of Steiner points (in red) added to a triangulation to improve the quality of triangles.

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]

References
  1. Hwang, F. K.; Richards, D. S.; Winter, P. (1992), The Steiner Tree Problem, Annals of Discrete Mathematics, 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.