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

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

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