2024-03-29T13:37:15Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001955202023-04-27T10:00:04Z01164:02592:09674:09784
内外相似パズルにおける困難性の証明と効率的なアルゴリズムResearch on Similar Hole Puzzle: Hardness and Efficient Algorithmjpnhttp://id.nii.ac.jp/1001/00195431/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=195520&item_no=1&attribute_id=1&file_no=1Copyright (c) 2019 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.北陸先端科学技術大学院大学北陸先端科学技術大学院大学樋本, 喬上原, 隆平内外相似パズルとは,複数の多角形からなるピース群を配置することで,出来上がった図形の外形と内側に空いた穴が互いに相似な図形にできるかどうかを判定するシルエットパズルの一種である.本稿では,内外相似パズルの困難性についての証明と,制約のある問題を多項式時間で解くアルゴリズムを示す.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.AN1009593X研究報告アルゴリズム(AL)2019-AL-1733132019-05-032188-85662019-04-16