Design of numerically robust geometric algorithms

数值鲁棒几何算法的设计

• 批准号: 04452191
• 负责人: SUGIHARA Kokichi
• 金额: $ 1.6万
• 依托单位: University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (B)
• 财政年份: 1992
• 资助国家: 日本
• 起止时间: 1992 至 1994
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-04452191/
• 关键词: Combinatorial Abstruction; Computational Geometry; Numerical Stability; Robustness; Voronoi Diagrams; Delaunay Decomposition; Combinatorial Geometry; 幾何アルゴリズム; 数値誤差対策; ソリッドモデリング; 制約つきドロネー分割; 幾何的アルゴリズム; 数値誤差; 組合せ幾何学; グリッド生成; 凸包構成; 交差図形

The design principle called "combinatorial abstraction", which was proposed by our research group for numerically robust geometric algorithms, has been studied from both theoretical and experimental points of view.This principle was successfully applied to the problems of constructing ordinary Voronoi diagrams in two- and three-dimensional space, constructing generalized Voronoi diagrams for line segments and for polygons, constructing three-dimensional convex hulls, intersecting convex polyhedra, constructing Laguerre Voronoi diagrams, constructing arrangements of line segments, and constructing Voronoi diagrams for arbitrary figures. Furthermore, it was found that this principle is applicable if the objects admit topological properties that can be checked efficiently.From a theoretical point of view, it became clear that the algorithm designed by this principle solves the geometric problem in the world of combinatorial geometry. From an experimental point of view, on the other hand, the computer programs made in this principle turned out to be completely robust in the sense that they never fail even if the arithmetic precision is poor.

本文从理论和实验两方面研究了本课题组提出的数值鲁棒几何算法的设计原则--组合抽象原则，并成功地应用于二维和三维空间中普通Voronoi图的构造、线段和多边形的广义Voronoi图的构造、三维凸包的构造、相交凸多面体，构造Laguerre Voronoi图，构造线段排列，构造任意图形的Voronoi图。此外，还发现，如果对象具有可以被有效检验的拓扑性质，则该原理是适用的。从理论的角度来看，很明显，由该原理设计的算法解决了组合几何世界中的几何问题。另一方面，从实验的角度来看，根据这一原理编制的计算机程序是完全健壮的，因为即使算术精度很差，它们也不会失败。

项目成果

稲垣宏: "3次元ボロノイ図構成のためのの数値的に安定な逐次添加法" 情報処理学会論文誌. 35. 1-10 (1994)

Hiroshi Inagaki：“三维 Voronoi 图构造的数值稳定顺序加法”日本信息处理学会杂志 35. 1-10 (1994)。

K.Sugihara: "Application of the Delaunay triangulation to geometric intersection problems" Lecture Notes in Control and Information Sciences(“System Modelling and Optimization",Proc.15th IFIP Conference). 180. 112-121 (1992)

K.Sugihara：“Delaunay 三角剖分在几何相交问题中的应用”控制与信息科学讲义（“系统建模与优化”，Proc.15th IFIP Conference）。

K.Sugihara: "Approximation of generalized Voronoi diagrams by ordinary Voronoi diagrams" CVGIP:Graphical Models and Processing. 55. 522-531 (1993)

K.Sugihara：“用普通 Voronoi 图近似广义 Voronoi 图” CVGIP：图形模型和处理。

K.Sugihara: "Voronoi diagrams in a river" International Journal of Computational Geometry and Applications. 2. 29-48 (1992)

K.Sugihara：“河流中的 Voronoi 图”国际计算几何与应用杂志。

K.Sugihara: "Simpler proof of a realizability theorrem on Delaunay triangulations" Information Processing Letters. 50. 173-176 (1994)

K.Sugihara：“关于 Delaunay 三角剖分的可实现性定理的简单证明”信息处理快报。