Steiner Minimal Trees

Abstract

A Steiner minimal tree for given points $A_1 , \cdots ,A_n $ in the plane is a tree which interconnects these points using lines of shortest possible total length. In order to achieve minimum length the Steiner minimal tree may contain other vertices (Steiner points) beside $A_1 , \cdots ,A_n $. We find conditions which simplify the task of constructing a Steiner minimal tree. Some of these use relationships with the easily constructed (ordinary) minimal tree which achieves minimum length among all trees having only $A_1 , \cdots ,A_n $ as vertices. Other questions concern the relative lengths of these two trees in extreme or typical cases. A review of the existing literature is included.