Steiner Point (computational Geometry) on:
[Wikipedia]
[Google]
[Amazon]
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
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
In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a ...
, named after Jakob Steiner
Jakob Steiner (18 March 1796 – 1 April 1863) was a Swiss mathematician who worked primarily in geometry.
Life
Steiner was born in the village of Utzenstorf, Canton of Bern. At 18, he became a pupil of Heinrich Pestalozzi and afterwards s ...
, 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
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...
. However, shorter networks can often be obtained by adding Steiner points,
and using both the new points and the input points as edge endpoints.
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.
See also
*Delaunay refinement In mesh generation, Delaunay refinement are algorithms for mesh generation based on the principle of adding Steiner points to the geometry of an input to be meshed, in a way that causes the Delaunay triangulation or constrained Delaunay triangulati ...
References
{{reflist Computational geometry