| 講演名 | 1997/11/14 直交順序を保存する矩形の非交差再配置問題について 林 邦彦, 井上 美智子, 増澤 利光, 藤原 秀雄, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 予め平面上に配置されているn個の矩形の集合に対して, 直交順序を保存し, 矩形同士が交差しない, という制約の下で, 面積最小の再配置を求める問題を, 直交順序を保存する矩形の面積最小非交差再配置問題と呼ぶ. Misueらは, この問題を解くO(n^2)時間の発見的アルゴリズムを提案した. 本稿ではまず, 直交順序を保存する非交差再配置がある面積以下で可能かどうかを判定する問題が, NP完全であることを証明する. さらに, Misueらの手法による結果よりも面積が小さい配置を求める, O(n^2)時間の発見的再配置アルゴリズムを与える. |
| 抄録(英) | For a given set of n rectangles placing on a plane, we consider a problem for finding the minimum area layout of the rectangles that avoids intersection of the rectangles and preserves the orthogonal order. Misue et al. proposed an O(n^2)-time heuristic algorithm for the problem. We first show that the decision problem for the minimum area layout (without intersection and with preserving the orthogonal order) is NP-complete. We also present a new O(n^2)-time heuristic algorithm for the problem that finds a layout with smaller area than Misue's. |
| キーワード(和) | グラフ / 描画 / アルゴリズム / 直交順序 / 計算量 |
| キーワード(英) | graph / drawing / algorithm / orthogonal ordering / complexity |
| 資料番号 | COMP97-65 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1997/11/14(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 直交順序を保存する矩形の非交差再配置問題について |
| サブタイトル（和） | |
| タイトル（英） | A Layout Adjustment Problem for Disjoint Rectangles Preserving Orthogonal Order |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ / graph |
| キーワード(2)（和/英） | 描画 / drawing |
| キーワード(3)（和/英） | アルゴリズム / algorithm |
| キーワード(4)（和/英） | 直交順序 / orthogonal ordering |
| キーワード(5)（和/英） | 計算量 / complexity |
| 第 1 著者 氏名（和/英） | 林 邦彦 / Kunihiko Hayashi |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学 情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 第 2 著者 氏名（和/英） | 井上 美智子 / Michiko Inoue |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学 情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 第 3 著者 氏名（和/英） | 増澤 利光 / Toshimitsu Masuzawa |
| 第 3 著者 所属（和/英） | 奈良先端科学技術大学院大学 情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 第 4 著者 氏名（和/英） | 藤原 秀雄 / Hideo Fujiwara |
| 第 4 著者 所属（和/英） | 奈良先端科学技術大学院大学 情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 発表年月日 | 1997/11/14 |
| 資料番号 | COMP97-65 |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 375 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |