文献

J-GLOBAL ID：202102220503409336   整理番号：21A0967719

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

Experimental Evaluation of a Dynamic-Programming-Based Algorithm for Enumerating Simple Polygonizations

著者 (4件)： 中畑裕 (京大 大学院情報学研究科) ,  堀山貴史 (北大 大学院情報科学研究院) ,  湊真一 (京大 大学院情報学研究科) ,  山中克久 (岩手大 理工)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2021  号： AL-182  ページ： Vol.2021-AL-182,No.5,1-8 (WEB ONLY)  発行年： 2021年03月10日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 平面上のn点に対し,それらn点を頂点とする単純多角形をsimple polygonizationという.平面上のn点が与えられたとき,simple polygonizationすべてを多項式遅延(解1つあたり多項式時間)で列挙できるかは計算幾何学分野における重要な未解決問題である.山中らは,simple polygonizationを拡張したsurrounding polygonに対し,逆探索法に基づく多項式遅延の手法を与えた.山中らはこの手法を実験的に評価し,凸包内部の点が少ない点集合に対して高速に動作することを報告したが,理論的裏付けは示されていない.一方,中畑らは,動的計画法に基づく指数時間の前処理ののち,simple polygonizationを多項式遅延で列挙する手法を与えたが,実験的評価は行われていない.本稿では,山中らの手法が凸包内部の点が少ない点集合に対して高速に動作することを裏付ける理論的解析を与える.また,中畑らの手法を効率化するための枝刈りを提案し,その枝刈りを用いることで,中畑らの手法を同様の入力に適用した際の計算量の上界を指数的に改善できることを理論的に示す.中畑らの手法を実験的に評価し,提案した枝刈りの効果を調べるとともに,山中らの手法や全探索法との比較を行う.(著者抄録)

シソーラス用語： 多角形 ,  *計算幾何学 ,  アルゴリズム ,  計算量 ,  計算理論 ,  凸包 ,  動的計画法 ,  木探索 ,  有向グラフ ,  評価試験
準シソーラス用語： *単純多角形化 ,  列挙アルゴリズム ,  多項式遅延 ,  枝刈り【木探索】 ,  DAG【グラフ】 ,  多項式時間

分類 (1件)： 計算理論  (JB02000A)

引用文献 (12件)：

• Erik Demaine. Simple polygonizations. https://erikdemaine.org/polygonization/. Accessed: February 22, 2021.
• Micha Sharir, Adam Sheffer, and Emo Welzl. Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn’s technique. J. Comb. Theory, Ser. A, 120(4):777-794, 2013.
• Alfredo García Olaverri, Marc Noy, and Javier Tejel. Lower bounds on the number of crossing-free subgraphs of KN. Comput. Geom., 16(4):211-221, 2000.
• Dániel Marx and Tillmann Miltzow. Peeling and nibbling the cactus: Subexponential-time algorithms for counting triangulations and related problems. In Proceedings of the 32nd Symposium on Computational Geometry, volume 51 of LIPIcs, pages 52:1-52:16, 2016.
• Chong Zhu, Gopalakrishnan Sundaram, Jack Snoeyink, and Joseph S. B. Mitchell. Generating random polygons with given vertices. Comput. Geom., 6:277-290, 1996.

タイトルに関連する用語 (4件)： 動的計画法 ,  アルゴリズム ,  実験 ,  評価