On orientation metric and euclidean Steiner tree constructions

We consider Steiner minimal trees (SMT) in the plane, where only orientations with angle i pi/sigma, 0 less than or equal to i less than or equal to sigma - 1 and sigma an integer, are allowed. The orientations define a metric, called the orientation metric, lambda(sigma), in a natural way. In particular, lambda(2) metric is the rectilinear metric and the Euclidean metric can be regarded as lambda(infinity) metric. In this paper, we provide a method to find an optimal lambda(sigma) SMT for 3 or 4 points by analyzing the topology of lambda(sigma) SMT's in great details. Utilizing these results and based on the idea of loop detection first proposed in [8], we further develop an O(n(2)) time heuristic for the general lambda(sigma) SMT problem, including the Euclidean metric. Experiments performed on publicly available benchmark data for 12 different metrics, plus the Euclidean metric, demonstrate the efficiency of our algorithms and the quality of our results.