固定パラメータ問題に対する高速算法に基づく計算困難問題の解決

• 資料種別: 文書・図像類
• タイトル: 固定パラメータ問題に対する高速算法に基づく計算困難問題の解決
• 著者・編者: 浅野, 哲夫; Asano, Tetsuo
• 著者標目: 浅野, 哲夫; Asano, Tetsuo
• 出版年月日等: 2008-05-26
• 出版年（W3CDTF）: 2008-05-26
• 並列タイトル等: Solving Computationally Hard Problems Based on Fast Algorithms for Fixed-Parameter Problems
• タイトル（掲載誌）: 平成18(2006)年度 科学研究費補助金 基盤研究(B) 研究成果報告書概要 = 2006 Fiscal Year Final Research Report Summary
• 巻号年月日等（掲載誌）: 2003 – 2006
• 掲載巻: 2003 – 2006
• 掲載ページ: 3p.-
• 本文の言語コード: jpn
• 件名標目: アルゴリズム; 計算幾何学; 固定パラメータ問題; 漸近解析; 計算複雑度; algorithm; computational geometry; fixed-parameter problem; asymptotic analysis; computational complexity
• 対象利用者: 一般
• 一般注記: 金沢大学 / 北陸先端科学技術大学院大学; 本研究の目的は、最近の計算機環境の下で固定パラメータ問題を高速に解決するための方法論を確立することである。そのために、単なるプログラムテクニックとして解析に反映されなかった側面を数学的に厳密に評価し、従来の解析方法とは全く異なる立場から計算の効率評価を行うことであった。今年度は、トライセクター曲線に関する研究に時間を割いた.平面上に与えられた2点に対する2等分線は容易に計算できるが,2点間に等距離の曲線を描くのは困難である.正確には,任意の精度で近似解を得ることはできるが,正確に曲線上の点を求めることは不可能(代数的でない)であることが予想される.本研究では,そのような曲線が常に存在し,ユニークに定まることを数学的にかつ構成的に証明した.それ以外にも様々な興味深い構造的な性質を明らかにした.この研究の成果は,5月に開かれた理論計算機科学では最高峰の国際会議であるSTOCにおいて発表すると共に,Advances in Mathematicsという数学ではトップクラスのジャーナルにも論文を発表した.非常に基本的な問題でありながら,これまでに全く類似の研究がなかったということはむしろ驚きである.計算幾何学においてボロノイ図は重要な研究課題のひとつである.本研究では,従来のボロノイ図の概念を一般化して,三角形に関する評価尺度に基づいた様々なボロノイ図を定義したが,特に角度ボロノイ図に興味をもち,その構造と複雑さに関する研究を行った.具体的には,線分の集合が与えられたとき,どの線分に対して定義される視角が最も小さいかという関係で平面を分割したものである.この研究では,角度ボロノイ図が通常のボロノイ図と極めて異なる性質をもつことを証明し,さらに最小の視角を最大にする点を効率よく求めるためのアルゴリズムを示している.この結果にっいては,7月に開かれたボロノイ図に関する国際ワークショップにおいて報告した.現在は,そのジャーナルバージョンを執筆中であり,近い将来にジャーナル誌に投稿をする予定である.; The purpose of this research is to establish methodology for solving fixed parameter problems in an efficient way under latest computer environment. For the purpose we mathematically evaluate some aspects of programming which has not been reflected to analysis as just simple programming techniques and then analyze computational performance from a completely different standpoint from the existing ones.In this year we spent much time for the study of distance trisector curves. Given two points in the plane, it is easy to draw perpendicular bisector, but it is hard to draw two curves equidistant from each other. More exactly, we can approximate points on the curves at any precision, but it is impossible to compute their coordinates exactly without any error. In fact we conjecture that the curves are non-algebraic. In this research we proved that such curves exist and they are unique, mathematically in a constructive manner. We also found many interesting properties of the curves. The resu lts were presented at an international symposium STOC, one of the top conference in the world in this area and also published in a top mathematical journal, Advances in Mathematics. It is rather surprising that it is quite simple and fundamental problem while there is no study on the curves. We also applied the idea to Voronoi diagrams, which is one of the most important research topics in computational geometry. In this research we defined various Voronoi diagrams based on criteria on goodness of triangles by generalizing the traditional Voronoi diagrams. More concretely, given a set of line segments in the plane, an angular Voronoi diagram is a partition of the plane into regions by the relation on which line segment gives the smallest visual angle. We have shown that this Voronoi diagram has properties which are quite different from those of the exisiting ones. We also gave an efficient algorithm for finding a point that maximizes the smallest visual angle. The results were presented at an international symposium on Voronoi diagrams We are now preparing journal version of those papers to submit them to international journals.; 研究課題/領域番号:15300003, 研究期間(年度):2003 - 2006; 出典：「固定パラメータ問題に対する高速算法に基づく計算困難問題の解決」研究成果報告書 課題番号15300003（KAKEN：科学研究費助成事業データベース（国立情報学研究所）） （https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-15300003/153000032006kenkyu_seika_hokoku_gaiyo/）を加工して作成
• DOI: 10.24517/00061991
• 一次資料へのリンクURL: https://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=55716&item_no=1&attribute_id=26&file_no=1
• オンライン閲覧公開範囲: 限定公開
• 著作権情報: CC BY-NC-ND
• 関連情報: https://kaken.nii.ac.jp/search/?qm=90113133; https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-15300003/; https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-15300003/153000032006kenkyu_seika_hokoku_gaiyo/
• 連携機関・データベース: 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）; https://irdb.nii.ac.jp
• 提供元機関・データベース: 金沢大学 : 金沢大学学術情報リポジトリKURA