Design of Precision-Guaranteed Geometric Algorithms

精度保证的几何算法的设计

• 批准号: 10205205
• 负责人: SUGIHARA Kokichi
• 金额: $ 6.85万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (B)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205205/
• 关键词: robust computation; exact computation; precision-guaranteed computation; Voronoi diagram; interval algebra; evaluation of errors; area without zero points; lazy evaluation; 多面体の表現; 誤差の伝幡; 有限要素法; 弾性変形; ソリッドモデリング; 誤差吸収列; 凸包; 剰余演算; 加速

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.

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

项目成果

K. Sugihara, M. Iri, H. Inagaki and T. Imai: "Topology-oriented implementation---An approach to robust geometric algorithms"Algorithmica. 27. 5-20 (2000)

K. Sugihara、M. Iri、H. Inagaki 和 T. Imai：“面向拓扑的实现——稳健几何算法的方法”Algorithmica。

杉原厚吉, 今井敏行: "工学のための応用代数"共立出版. 174 (1999)

Atsuyoshi Sugihara、Toshiyuki Imai：“工程应用代数”Kyoritsu Shuppan 174 (1999)。

Hisamoto Hiyoshi , Kokichi Sugihara: "An interpolant based on line segment Voronoi diagrams"Discrete and Computational Geometry, Lecture Notes in Computer Science. 1763. 119-128 (2000)

Hisamoto Hiyoshi、Kokichi Sugihara：“基于线段 Voronoi 图的插值”离散与计算几何，计算机科学讲义。

畑口剛之、杉原厚吉: "線分の交点列挙問題に対する平面走査法の改良" 日本応用数理学会論文誌. 8・2. 257-274 (1998)

Takeyuki Hataguchi、Atsukichi Sugihara：“枚举线段交点问题的平面扫描方法的改进”日本应用数学学会会刊 8・2（1998）。

H. Hiyoshi and K. Sugihara: "Two generalizations of an interpolant based on Voronoi diagrams"International Journal of Shape Modeling. 5. 219-231 (1999)

H. Hiyoshi 和 K. Sugihara：“基于 Voronoi 图的插值的两种推广”国际形状建模杂志。