| 大会名称 |
|---|
| 2010年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2010 |
| 発行日 |
| 2010/8/20 |
| セッション番号 |
| 7A |
| セッション名 |
| アルゴリズム・コンピュテーション(3) |
| 講演日 |
| 2010/09/09 |
| 講演場所(会議室等) |
| A会場（総合学習プラザ1F 第5講義室） |
| 講演番号 |
| RA-005 |
| タイトル |
| Enumerating bottom-left stable positions for rectangles with overlap |
| 著者名 |
| 今堀 慎治, 簡 于耀, 田中 勇真, 柳浦 睦憲, |
| キーワード |
| rectangle packing, bottom-left stable position |
| 抄録 |
|
We consider the problem of enumerating bottom-left stable positions for a given layout of rectangles. We propose an algorithm that enumerates all the bottom-left stable positions in O((n+K) log n) time, where n is the number of placed rectangles and K is the number of bottom-left stable positions (i.e., size of the output). Our algorithm works for layouts without bottom-left stability and with overlaps. Even for instances with more than one million placed rectangles, the proposed algorithm works in a short computation time. |
| 本文pdf |
| PDF download (206KB) |