Exact location of the Steiner point of the three-point Steiner minimum tree in ?-geometry
Michiyoshi Hayase · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 2000
The exact location of the Steiner point in the Steiner minimum tree (SMT) for three given points in the λ-geometry plane is shown. SMTs are important to layout of LSIs and printed boards in rectilinear geometry and to constructing networks with shortest paths in Euclidean geometry. The λ-geometry that is introduced to fill the gap between the two geometries allows only orientations with angles (iπ/λ) for all i, where i and λ (λ ⩾ 2) are integers. First, the exact location of the Steiner point is determined for three-point SMT. Surprisingly, when λ ≡ 0 (mod 3) there are infinite candidate points of the Steiner point. Next, two conditions for the locations of the three points are determined for the SMT whose total length of edges is shorter than that of the corresponding minimum spanning tree (MST), and is equal to that of the corresponding MST. © 2000 Scripta Technica, Electron Comm Jpn Pt 3, 84(2): 84–94, 2001