2026-04-19T12:11:55Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00080303 2025-01-21T19:51:58Z 1164:2592:6670:6671

辞書式最適化に基づく三角形分割における辺挿入パラダイム Edge insertion paradigm for triangulation with lexicographical optimization 大瀧, 史 玉木, 久夫 Fumihito, Ohtaki Hisao, Tamaki ショートトーク 一定の条件を満たす最適化基準において，最悪値に関して最適な三角形分割を求める多項式時間アルゴリズムのひとつに辺挿入パラダイムがある．このアルゴリズムは辞書式の最適化にも拡張できるが，その適用に際しては入力の点集合に制約条件が課される．一般に，応用上では三角形分割は使用する三角形がつぶれていない方が良いとされているため，すべての三角形の評価値が問題となるので，最悪値最適化よりも辞書式最適化の方が望ましい．本稿では，制約条件を満たさない入力に対して辺挿入パラダイムを適用したときの解の質を，真の最適解と比較することにより実験的に評価する． Edge insertion paradigm is one of the polynomial-time algorithms for optimal triangulation, which can be applied when the objective function satisfies certain conditions. This algorithm, which is primarily for optimizing with the worst-triangle measure, can be extended to the lexicographic measure, but with certain restrictions on the input point set. In practice, the lexicographic measure is preffered to worst-triangle measure, since the quality of all triangles are relevant. In this note, we experimentarilly evaluate the quality of solutions obtained by the edge insertion paradigm, applied to input point sets violating the restriction, comparing them with the true lexicographically optimal solutions. 情報処理学会 2012-01-21 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/80303 AN1009593X 研究報告アルゴリズム（AL） 2012-AL-138 5 1 7 https://ipsj.ixsq.nii.ac.jp/record/80303/files/IPSJ-AL12138005.pdf application/pdf 219.6 kB 2014-01-21