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]

See also

edit

References

edit
  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

📚 Artikel Terkait di Wikipedia

Jakob Steiner

Parallel axes rule Steiner–Lehmus theorem Steiner inellipse Steinerian Steiner point (computational geometry) Steiner point (triangle) "Steiner (print-only)"

Steiner point

A Steiner point (named after Jakob Steiner) may refer to: Steiner point (computational geometry), a point added in solving a geometric optimization problem

Synthetic geometry

Synthetic geometry (sometimes referred to as axiomatic geometry or even pure geometry) is geometry without the use of coordinates. It relies on the axiomatic

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

Outline of geometry

Absolute geometry Affine geometry Algebraic geometry Analytic geometry Birational geometry Complex geometry Computational geometry Conformal geometry Constructive

List of books in computational geometry

list of books in computational geometry. There are two major, largely nonoverlapping categories: Combinatorial computational geometry, which deals with

Triangulation (geometry)

Kreveld, Marc van; Overmars, Mark H.; Schwarzkopf, Otfried (2000). Computational geometry: algorithms and applications (2 ed.). Berlin Heidelberg: Springer

Multiple line segment intersection

In computational geometry, the multiple line segment intersection problem supplies a list of line segments in the Euclidean plane and asks whether any