权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Solving Computationally Hard Problems Based on Fast Algorithms for Fixed-Parameter Problems

基于固定参数问题的快速算法解决计算难题

基本信息

批准号：
15300003
负责人：
ASANO Testuo
金额：
$ 10.37万
依托单位：
JapanAdvanced Institute of Science and Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2006
项目状态：
已结题

项目摘要

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 … More 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. Less

本研究的目的是建立在最新的计算机环境下有效地解决固定参数问题的方法。为了这个目的，我们在数学上评估编程的某些方面，这些方面还没有反映到分析中，只是简单的编程技术，然后从与现有技术完全不同的角度分析计算性能。在这一年中，我们花了很多时间研究距离三等分曲线。给定平面上的两点，画垂直平分线很容易，但画两条等距曲线很难。更确切地说，我们可以以任何精度近似曲线上的点，但不可能精确地计算它们的坐标而没有任何误差。事实上，我们猜想曲线是非代数的。在这项研究中，我们证明了这样的曲线存在，他们是唯一的，在数学上的建设性的方式。我们还发现了曲线的许多有趣的性质。结果 ...更多信息它在国际研讨会STOC上发表，STOC是世界上这一领域的顶级会议之一，也发表在顶级数学杂志《数学进展》上。令人惊讶的是，这是一个非常简单和基本的问题，而没有对曲线进行研究。我们还将这个想法应用到Voronoi图，这是计算几何中最重要的研究课题之一。在本研究中，我们借由推广传统的Voronoi图，定义了各种基于三角形优度准则的Voronoi图。更具体地，给定平面中的一组线段，角度Voronoi图是通过线段给出最小视角的关系将平面划分为区域。我们已经证明了这种Voronoi图的性质是非常不同的那些的crackiting。我们还给出了一个有效的算法，找到一个点，最大化最小的视角。研究结果在一个关于Voronoi图的国际研讨会上发表。我们现在正在准备这些论文的期刊版本，以便提交给国际期刊。少