Variations on the Euclidean Steiner Tree Problem and Algorithms

Authors

Jack Holby, St. Lawrence University

Abstract

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.

Author Bio

Jack Holby, a native of Upper Black Eddy, Pennsylvania, graduated magna cum laude and Phi Beta Kappa from St. Lawrence University in 2014. Jack majored in Mathematics and minored in both Economics and Asian Studies. He enjoys skiing, the outdoors, and yoga. Currently, Jack works as an analyst for The Carlyle Group in New York City. He hopes to attend business school and/or graduate school studying mathematical economics.

Faculty Sponsor

Sam Vandervelde

Recommended Citation

Holby, Jack (2017) "Variations on the Euclidean Steiner Tree Problem and Algorithms," Rose-Hulman Undergraduate Mathematics Journal: Vol. 18: Iss. 1, Article 7.
Available at: https://scholar.rose-hulman.edu/rhumj/vol18/iss1/7