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 上提出，该研讨会是该领域的世界顶级会议之一，并且还发表在顶级数学期刊上。 ,数学的进展令人惊讶的是，这是一个非常简单和基本的问题，但我们也将这个想法应用到了Voronoi图上，这是本研究中最重要的研究主题之一。我们通过推广传统的 Voronoi 图，基于三角形的优度标准定义了各种 Voronoi 图。更具体地说，给定平面中的一组线段，角度 Voronoi 图是通过关系将平面划分为区域。我们已经证明，这个 Voronoi 图具有与现有的那些完全不同的属性，我们还给出了一种有效的算法来寻找最大化最小视角的点。在 Voronoi 图国际研讨会上发表我们现在正在准备这些论文的期刊版本，以便将其提交给国际期刊 Less。