Options
On orientation metric and Euclidean Steiner tree constructions
Author(s)
Date Issued
1998
Publisher
IEEE
ISSN
02714310
Citation
Proceedings - IEEE International Symposium on Circuits and Systems, 1998, vol. 6, pp. 241 - 243
Type
Conference Proceedings
Abstract
We consider Steiner minimal trees (SMT) in the plane, where only orientations with angle iπ/σ, 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 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 details. Utilizing these results and based on the idea of loop detection first proposed in, 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.
Loading...
Availability at HKSYU Library
