ISSN:
1573-2886
Keywords:
Steiner tree problems
;
orientation metric
;
rectilinear metric
;
Euclidean metric
;
heuristics
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract We consider Steiner minimum trees (SMT) in the plane, where only orientations with angle $${\sigma }$$ , 0 ≤ i ≤ σ − 1 and σ an integer, are allowed. The orientations define a metric, called the orientation metric, λσ, in a natural way. In particular, λ2 metric is the rectilinear metric and the Euclidean metric can beregarded 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 details. Utilizing these results and based on the idea of loop detection first proposed in Chao and Hsu, IEEE Trans. CAD, vol. 13, no. 3, pp. 303–309, 1994, we further develop an O(n2) 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1009837006569
Permalink
