An O(n log n) time and O(n) space algorithm for the Euclidean Steiner tree
problem with four terminals in a simple polygon with n vertices is given. Its
applicability to the problem of determining good quality solutions for any
number of terminals is discussed.
DIMACS Home Page