On orientation metric and Euclidean Steiner tree constructions

We consider Steiner minimal trees (SMT) in the plane, where only orientations with angle iπ/σ, 0⩽i⩽σ-1 and a an integer, are allowed. The orientations define a metric, called the orientation metric, λ_σ, in a natural way. In particular, λ₂ metric is the rectilinear metric and the Euclidean metric can be regarded as λ_∞ metric. In this paper, we provide a method to find an optimal λ _σ SMT for 3 or 4 points by analyzing the topology of λ_σ SMT´s in great detail. Utilizing these results and based on the idea of loop detection, we further develop an O(n²) time heuristic for the general λ_σ 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