直交順序を保存する方形の最小面積非交差再配置問題
スポンサーリンク
概要
- 論文の詳細を見る
あらかじめ平面上に配置されているn個の方形の集合に対して, 直交順序を保存し, 方形同士が交差しない, という制約のもとで, 面積最小の再配置を求める問題について考察する. 三末らはこの問題に対し, O(n^2)時間の発見的アルゴリズムを提案した. 本論文ではまず, ある面積以下で再配置可能かどうかを判定する問題が, NP完全であることを証明する. 更に, 面積最小の再配置を求めるO(n^2)時間の発見的再配置アルゴリズムを与え, このアルゴリズムで得られる再配置面積が, 三末らの手法で得られる面積以下であることを証明する. また, ランダムな初期配置に対して計算機実験を行い, 特に方形数が多い場合に, 三末らの結果に比べて15〜20%の面積で再配置できることを示す.
- 社団法人電子情報通信学会の論文
- 1999-06-25
著者
-
藤原 秀雄
奈良先端科学技術大学院大学 情報科学研究科
-
井上 美智子
奈良先端科学技術大学院大学情報科学研究科
-
林 邦彦
奈良先端科学技術大学院大学情報科学研究科:(現)松下電器産業株式会社
-
増澤 利光
奈良先端科学技術大学院大学情報科学研究科
-
井上 美智子
奈良先端科学技術大学院大学
-
井上 美智子
奈良先端科学技術大学院大学 情報科学研究科:科学技術振興機構crest
-
井上 美智子
奈良先端科学技大学院大学
関連論文
- セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について (コンカレント工学)
- セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について (信号処理)
- セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について (VLSI設計技術)
- セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について (回路とシステム)
- 部分スルー可検査性に基づく順序回路のテスト生成法(ディペンダブルコンピューティング)
- 共有メモリシステムにおける調停木スキップ相互排除アルゴリズム
- マルチクロック・ドメイン・コアテストのための再構成可能ラッパーの一構成法(テスト容易化設計,デザインガイア2008-VLSI設計の新しい大地)
- マルチクロック・ドメイン・コアテストのための再構成可能ラッパーの一構成法(テスト容易化設計,デザインガイア2008-VLSI設計の新しい大地-)
- セキュアスキャン設計のためのシフトレジスタ等価回路の列挙と合成
- 内蔵プロセッサを利用したマイクロコントローラのテスト高速化に関する考察