Design of Precision-Guaranteed Geometric Algorithms

几何算法是一项重要的技术，在地理信息系统、模式识别、机器人运动规划、计算机图形学和有限元分析等领域有着广泛的应用。它们在计算几何中得到了研究，但对数值误差并不一定具有鲁棒性。本项目的目标是使用保证精度的计算来克服这一困难。提出了一种新的设计几何算法的原理。该原理包括计算误差评估、精确计算、使用浮点滤波器加速计算、避免退化的符号摄动和另一种基于图形硬件的加速方法。将该原理应用于三维Delaunay图的构建，并将其应用于网格生成和广义Voronoi图的构建，用于体育团队合作的评价。对于更困难的几何问题，如晶体Voronoi图的构造，我们开发了另一种鲁棒方法。在该方法中，将几何问题用偏微分方程的形式重新表述，并使用有限差分法，特别是快速推进法来求解。将该方法应用于机器人运动规划中，计算了敌方机器人之间的无碰撞最短路径，证明了该方法比以前的方法更有效。

Geometric algorithms are important techniques and have many applications in geographic information system, pattern recognition, robot motion planning, computer graphics and finite element analysis. They are studied in computational geometry, but are not necessarily robust against numerical errors. The goal of this project is to overcome this difficulty using precision-guaranteed computation.We developed a new principle for designing numerically robust geometric algorithm. This principle consists of the evaluation of computational errors, exact-precision computation, acceleration of computation using floating- point filter, symbolic perturbation for avoiding degeneracy, and another acceleration method based on graphics hardware. This principle was applied to the construction of three-dimensional Delaunay diagrams and its application to mesh generation and the construction of a generalized Voronoi diagram for the evaluation of teamwork in sports.For more difficult geometric problems such as the construction of the crystal Voronoi diagram, we developed another robust method. In this method, the geometric problem is reformulated in terms of a partial differential equation, and is solved using finite-difference method, the fast-marching method, in particular. We applied this method to the robot motion planning, in which the collision-free shortest path among enemy robots is computed, and could prove that our new method is more efficient than previous methods.