| Item type |
SIG Technical Reports(1) |
| 公開日 |
2019-05-03 |
| タイトル |
|
|
タイトル |
内外相似パズルにおける困難性の証明と効率的なアルゴリズム |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Research on Similar Hole Puzzle: Hardness and Efficient Algorithm |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
北陸先端科学技術大学院大学 |
| 著者所属 |
|
|
|
北陸先端科学技術大学院大学 |
| 著者所属(英) |
|
|
|
en |
|
|
Japan Advanced Institute of Sciene and Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Japan Advanced Institute of Sciene and Technology |
| 著者名 |
樋本, 喬
上原, 隆平
|
| 著者名(英) |
Takashi, Himoto
Ryuhei, Uehara
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
内外相似パズルとは，複数の多角形からなるピース群を配置することで，出来上がった図形の外形と内側に空いた穴が互いに相似な図形にできるかどうかを判定するシルエットパズルの一種である．本稿では，内外相似パズルの困難性についての証明と，制約のある問題を多項式時間で解くアルゴリズムを示す． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Similar Hole Puzzle is one of the silhouette puzzles. Given a set of simple polygons,we decide if they form the silhouette such that the outside shape and its unique hole shape are similar. In this paper, we show that the problem is strongly NP-complete even if the pieces are quite restricted. AIso, we show that the problem can be solved in polynomial time if the number of pieces is a fixed constant. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2019-AL-173,
号 3,
p. 1-3,
発行日 2019-05-03
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL19173003.pdf (567.7 kB)
