The role of Steiner hulls in the solution to Steiner tree problems

ASteiner tree problem on the plane is that of finding a minimum lengthSteiner tree connecting a given setK ofterminals and lying within a given regionR of the Euclidean plane; it includes as special cases the Euclidean Steiner minimal tree problem (ESMT), the rectilinear Steiner tree problem (RST), and the Steiner tree problem on graphs (STG). ASteiner hull forK inR generically refers to any subregion ofR known to contain a Steiner tree. This paper gives a survey of the role of Steiner hulls in the Steiner tree problem. The significance of Steiner hulls in the efficient solution of Steiner tree problems is outlined, and then a compendium is given of the known Steiner hull constructions for ESMT, RST, and STG problems.