4つの端子からの距離の和が小さい領域を求めるアルゴリズム

スポンサーリンク

概要

論文の詳細を見る
いくつかの特定の地点から,距離の総和が小さい場所を見つける問題はいろいろな場面で現れる.例えば,自分のアパートの場所を決めるときに,学校,駅,コンビニ,郵便局,病院等により近い場所を望むのはよくあることである.またVLSIの多層配線においては,配線のショートを防ぐために"ビア"を配置して配線の層を変える.その際,各端子からの距離の総和の最小の場所にビアを配置することが望まれる.平面上に入力として正の定数lおよび4つの端子といくつかの長方形障害物が与えられるとする.このとき4つの端子からの距離の和がlより小さい領域,すなわち最適領域Rを求めるアルゴリズムを与える.ただし本報告で用いる距離はL_1-距離であるとする.そのアルゴリズムはO(K+n)の記憶量を用いてO((K+n)log n)時間で最適領域Rを求める.ここで,nは障害物の個数であり,Kは多角形Rの頂点数であるとする.すなわち,出力される最適領域はK角形である.
社団法人電子情報通信学会の論文
1996-03-11

著者

関連論文

もっと見る

スポンサーリンク