NP-hardness and a PTAS for the Euclidean Steiner Line Problem

Simon Bartlmae, Paul J. Jünger, Elmar Langetepe

The Euclidean Steiner Tree Problem (EST) seeks a minimum-cost tree interconnecting a given set of terminal points in the Euclidean plane, allowing the use of additional intersectio…