8 0 0 0 複合長方形領域の最小分割
- 著者
- 大附 辰夫 佐藤政生 橘 昌良 鳥居 司郎
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.24, no.5, pp.647-653, 1983-09-15
- 被引用文献数
- 1
複合長方形領域を重複なく最小個の長方形に分割する問題を扱う.ここでは 複合長方形領域が中空部分(窓)を含んだり 複数個の連結成分から成っているような一般的な場合を考察する.分割手順は二つのアルゴリズムから成っている.1番目のアルゴリズムは 縮退していない複合長方形領域を最小個の長方形に分割するものである.同じXまたはY座標上の二つの凹点間が領域内であるとき 複合長方形領域は縮退しているといい そうでない場合には縮退していないという.2番目のアルゴリズムは 与えられた(縮退している)複合長方形領域を最適にいくつかの縮退していない複合長方形領域に分解するものである.複合長方形領域の頂点の数をnとすると 1番目のアルゴリズムの計算複雑度はO(n log n)となり 2番目のアルゴリズムはO(n^5/2)となることを報告する.ここで扱う問題は LSI のアートワーク処理 画像処理 図形データベースなどにおける基本的問題の一つである.
1 0 0 0 OA ラバーバンドモデルに基づいた逐次配線手法の実装
- 著者
- 粟島 亨 田中 博 福井 省三 佐藤政生 大附 辰夫
- 雑誌
- 情報処理学会研究報告システムLSI設計技術(SLDM)
- 巻号頁・発行日
- vol.1992, no.43(1992-SLDM-062), pp.229-243, 1992-05-27
径路トポロジーの標準形であるラバーバンド表現に基づいた単層2点間ネットに対する逐次配線手法を提案する.本手法はトポロジー的に存在する径路は必ず発見することができる.また,最終段階に行われる幾何学的変換処理によって,径路の押し退け,すなわち,shove asidingが自然に実現できる.本手法を可視グラフを基本探索構造として計算機上に実装し,いくつかの例題に適用することにより,その有効性を実証した.
1 0 0 0 スケッチレイアウトシステムにおけるBGAパッケージ配線手法
- 著者
- 柴田 修一 鵜飼 薫 戸川 望 佐藤 政生 大附 辰夫
- 出版者
- 一般社団法人 エレクトロニクス実装学会
- 雑誌
- 回路実装学会誌 (ISSN:13410571)
- 巻号頁・発行日
- vol.12, no.4, pp.241-246, 1997
- 被引用文献数
- 7
BGA (Ball Grid Array) パッケージの平面配線問題は, ピンーパッドのマッピング問題として定式化される。本論文では, 位相レイアウトモデルに基づいたスケッチレイアウトシステムにおけるBGA配線手法を提案する。提案手法は, 各配線を対角線上に存在するピンから離れたピン間を通過させることにより, 最大混雑度および最大配線長の減少を可能とし, 同一周上のピン列におけるピッチを通過する配線本数の差を1に抑えることができる。提案手法を計算機上に実装し, 評価した結果を報告する。
1 0 0 0 OA 複合長方形領域の最小分割
複合長方形領域を重複なく最小個の長方形に分割する問題を扱う.ここでは 複合長方形領域が中空部分(窓)を含んだり 複数個の連結成分から成っているような一般的な場合を考察する.分割手順は二つのアルゴリズムから成っている.1番目のアルゴリズムは 縮退していない複合長方形領域を最小個の長方形に分割するものである.同じXまたはY座標上の二つの凹点間が領域内であるとき 複合長方形領域は縮退しているといい そうでない場合には縮退していないという.2番目のアルゴリズムは 与えられた(縮退している)複合長方形領域を最適にいくつかの縮退していない複合長方形領域に分解するものである.複合長方形領域の頂点の数をnとすると 1番目のアルゴリズムの計算複雑度はO(n log n)となり 2番目のアルゴリズムはO(n^5/2)となることを報告する.ここで扱う問題は LSI のアートワーク処理 画像処理 図形データベースなどにおける基本的問題の一つである.