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

Material type: 文書・図像類

Author: 浅野, 哲夫ほか

Publisher: -

Publication date: 2008-05-26

Material Format: Digital

Capacity, size, etc.: -

NDC: -

View All

Notes on use

Note (General)：: 金沢大学 / 北陸先端科学技術大学院大学本研究の目的は、最近の計算機環境の下で固定パラメータ問題を高速に解決するための方法論を確立することである。そのために、単なるプログラムテクニックとして解析に反映されなかった側面を数学的に厳密に評価し、従来の解析方法とは全く異なる立場から計算の効率評価を行うこと...

Related materials as well as pre- and post-revision versions

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/

Search by Bookstore

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

Kanazawa University Repository for Academic Resources
Digital
You can check the holdings of institutions and databases with which 学術機関リポジトリデータベース（IRDB）（機関リポジトリ） is linked at the site of 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）.
Kanazawa University Repository for Academic Resources

Search by Bookstore

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: 文書・図像類
Title: 固定パラメータ問題に対する高速算法に基づく計算困難問題の解決
Author/Editor: 浅野, 哲夫
Asano, Tetsuo
Author Heading: 浅野, 哲夫
Asano, Tetsuo
Publication Date: 2008-05-26
Publication Date (W3CDTF): 2008-05-26
Alternative Title: Solving Computationally Hard Problems Based on Fast Algorithms for Fixed-Parameter Problems
Periodical title: 平成18(2006)年度科学研究費補助金基盤研究(B) 研究成果報告書概要 = 2006 Fiscal Year Final Research Report Summary
No. or year of volume/issue: 2003 – 2006
Volume: 2003 – 2006
Pages: 3p.-
Text Language Code: jpn
Subject Heading: アルゴリズム
計算幾何学
固定パラメータ問題
漸近解析
計算複雑度
algorithm
computational geometry
fixed-parameter problem
asymptotic analysis
computational complexity
Target Audience: 一般
Note (General): 金沢大学 / 北陸先端科学技術大学院大学
本研究の目的は、最近の計算機環境の下で固定パラメータ問題を高速に解決するための方法論を確立することである。そのために、単なるプログラムテクニックとして解析に反映されなかった側面を数学的に厳密に評価し、従来の解析方法とは全く異なる立場から計算の効率評価を行うことであった。今年度は、トライセクター曲線に関する研究に時間を割いた.平面上に与えられた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
Source: https://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=55716&item_no=1&attribute_id=26&file_no=1
https://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=55716&item_no=1&attribute_id=26&file_no=1
Access Restrictions: 限定公開
Rights (production): CC BY-NC-ND
Related Material: 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/
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 金沢大学 : 金沢大学学術情報リポジトリKURA