The Euclidean Steiner Tree Problem

The Euclidean Steiner tree problem is solved by finding the tree with minimal Euclidean length spanning a set of fixed vertices in the plane, while allowing for the addition of auxiliary vertices (Steiner vertices). Steiner trees are widely used to design real-world structures like highways and oil pipelines. Unfortunately, the Euclidean Steiner Tree Problem has shown to be NP-Hard, meaning there are no currently known polynomial time algorithms. This paper presents a brief history of the problem and discusses two techniques for finding Steiner trees. 1