The Euclidean Steiner Tree Problem (ESTP) involves creating a minimal spanning network of a set of points by allowing the introduction of new points, called Steiner points. This paper discusses a variation on this classic problem by introducing a single Steiner line‚ whose weight is not counted in the resulting network, in addition to the Steiner points. For small sets, we arrive at a complete geometric solution. We discuss heuristic algorithms for solving this variation on larger sets. We believe that, in general, this problem is NP-hard.
Sam Vandervelde, Proof School, 555 Post St., San Francisco, CA 94102
"Variations on the Euclidean Steiner Tree Problem and Algorithms,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 18
, Article 7.
Available at: http://scholar.rose-hulman.edu/rhumj/vol18/iss1/7