Name
Abstract | ||
|---|---|---|
We consider Steiner minimum trees (SMT) in the plane, where only orientations with angle
$${\sigma }$$
, 0 = i = s - 1 and s an integer, are allowed. The orientations define a metric, called the orientation metric, ?s, in a natural way. In particular, ?2 metric is the rectilinear metric and the Euclidean metric can beregarded as ?8 metric. In this paper, we provide a method to find an optimal ?s SMT for 3 or 4 points by analyzing the topology of ?s 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 ?s 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. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1023/A:1009837006569 | J. Comb. Optim. |
Keywords | Field | DocType |
Steiner tree problems,orientation metric,rectilinear metric,Euclidean metric,heuristics | Equivalence of metrics,Mathematical optimization,Fisher information metric,Combinatorics,Euclidean distance,Metric tree,Convex metric space,Metric (mathematics),Intrinsic metric,Metric space,Mathematics | Journal |
Volume | Issue | ISSN |
4 | 1 | 1573-2886 |
Citations | PageRank | References |
5 | 0.71 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Y. Y. Li | 1 | 5 | 0.71 |
| Kwong-Sak Leung | 2 | 1887 | 205.58 |
| C. K. Wong | 3 | 1459 | 513.44 |