動的計画法に基づくSimple Polygonization列挙アルゴリズムの実験的評価

• Item type: SIG Technical Reports(1)
• 公開日: 2021-03-10
• タイトル: 動的計画法に基づくSimple Polygonization列挙アルゴリズムの実験的評価
• タイトル / 言語: en
• タイトル: Experimental Evaluation of a Dynamic-Programming-Based Algorithm for Enumerating Simple Polygonizations
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: 北海道大学大学院情報科学研究院
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: 岩手大学理工学部
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Engineering, Iwate University
• 著者名: 中畑, 裕; 堀山, 貴史; 湊, 真一; 山中, 克久
• 著者名(英): Yu, Nakahata; Takashi, Horiyama; Shin-ichi, Minato; Katsuhisa, Yamanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面上の n 点に対し，それら n 点を頂点とする単純多角形を simple polygonization という．平面上の n 点が与えられたとき，simple polygonization すべてを多項式遅延（解 1 つあたり多項式時間）で列挙できるかは計算幾何学分野における重要な未解決問題である．山中らは，simple polygonization を拡張した surrounding polygon に対し，逆探索法に基づく多項式遅延の手法を与えた．山中らはこの手法を実験的に評価し，凸包内部の点が少ない点集合に対して高速に動作することを報告したが，理論的裏付けは示されていない．一方，中畑らは，動的計画法に基づく指数時間の前処理ののち，simple polygonization を多項式遅延で列挙する手法を与えたが，実験的評価は行われていない．本稿では，山中らの手法が凸包内部の点が少ない点集合に対して高速に動作することを裏付ける理論的解析を与える．また，中畑らの手法を効率化するための枝刈りを提案し，その枝刈りを用いることで，中畑らの手法を同様の入力に適用した際の計算量の上界を指数的に改善できることを理論的に示す．中畑らの手法を実験的に評価し，提案した枝刈りの効果を調べるとともに，山中らの手法や全探索法との比較を行う．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2021-AL-182, 号 5, p. 1-8, 発行日 2021-03-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会