λ-幾何における3点の最小スタイナ木のスタイナ点位置

早瀬 道芳  

誌名
電子情報通信学会論文誌 A   Vol.J81-A   No.12   pp.1774-1782
発行日: 1998/12/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: アルゴリズムとデータ構造計算複雑度
キーワード: 
最小スタイナ木,  自動設計,  ネットワーク,  λ-幾何,  

本文: PDF(593KB)>>
論文を購入




あらまし: 
スタイナ木は,x-y平面上に与えられた点の集合に必要に応じて新たな点(スタイナ点と呼ぶ)を追加して,点間を枝で接続した木である.特に,枝の長さの和が最小になる木を「最小スタイナ木」という.最小スタイナ木問題は,ネットワーク配置やVLSIの配線の最短経路問題として発展してきた.前者は,任意方向の線分を許すユークリッド幾何における最短経路を求める問題であり,後者は,水平方向と垂直方向の線分のみを許す直交幾何における最短経路を求める問題である.ユークリッド幾何と直交幾何の間を埋める「λ-幾何」は,線分の方向を水平方向とπ/λ(λ≧2)の整数倍の方向のみに限定した幾何である.本論文では,任意に与えられた3点に対するλ-幾何の最小スタイナ木のスタイナ点の位置の厳密解を示した.3点に対する最小スタイナ木のスタイナ点はたかだか1個であるので,スタイナ点の位置を決めれば最小スタイナ木は決まる.まず,最小スタイナ木のスタイナ点の位置と3点の位置関係を示した.そして,λ0(mod3)の場合には,最小スタイナ木のスタイナ点の候補位置が,驚くことに無限個あり得ることを示した.次いで,最小スタイナ木の枝長和が最小全域木と一致する場合,及び,最小スタイナ木の枝長和が最小全域木より小さくなる場合の3点の位置関係も示した.