Construction of a Topology-Oriented Geometric System

面向拓扑的几何系统的构建

• 批准号: 05555027
• 负责人: SUGIHARA Kokichi
• 金额: $ 3.2万
• 依托单位: UNIVERSITY OF TOKYO
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Developmental Scientific Research (B)
• 财政年份: 1993
• 资助国家: 日本
• 起止时间: 1993 至 1995
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-05555027/
• 关键词: computational geometry; numerical error; topology-oriented method; image processing; Voronoi diagram; 3-d convex hull; mesh generation; numerical stability; 衝突回避経路探索; ドロネ-図; 多角形ボロノイ図; 骨格線抽出; 幾何アルゴリズム; ドロネー図; 凸多面体; 交差図形

The topology-oriented method for designing geometric algorithms was applied to fundamental problems in computational geometry. This year in particular, numerically stable softwares for incremental constrution of the Voronoi diagrams for polygons, for Minkowski operations between polygons, and for divide-and-conquer construction of three-dimensional convex hulls were developed. Also the manuals of some of these softwares together with other ones developed previously were constructed.A topology-oriented algorithm solves a geometric problem in the world of combinational geometry, and hence the output is not necessarily consistent with Euclidean geometry. The distance between the correct answer and the output was analyied both from a theoretically point of view and an experimental point of view.Applications of the topology-oriented algorithm were also considered. The Delaunay tirangulation with numerical disturbance was applied to finite-element analysis, and a new scheme for the finite-element analysis was proposed. This scheme is practical in the sense that it works stably even if the Delaunay mesh is incomplete.

将面向拓扑的几何算法设计方法应用于计算几何中的基本问题。特别是今年，开发了数值稳定的软件，用于多边形的Voronoi图的增量扩展，多边形之间的Minkowski运算，以及三维凸包的分治构造。同时，结合已有的一些软件，编写了相应的使用手册。面向拓扑的算法求解的是组合几何中的几何问题，其结果不一定与欧几里德几何一致。从理论和实验两方面分析了正确答案与输出之间的距离，并讨论了面向拓扑算法的应用。将带数值扰动的Delaunay网格法应用于有限元分析，提出了一种新的有限元分析方法。该方法在Delaunay网格不完整的情况下也能稳定地工作，是一种实用的方法。

项目成果

K.Sugihara: "A robust topology-oriented incremental algorithm for Voronoi diagrams" International Journal of Computational Geometry and Applications. 4. 179-228 (1994)

K.Sugihara：“用于 Voronoi 图的稳健的面向拓扑的增量算法”国际计算几何与应用杂志。

伊理正夫,他: "計算幾何学と地理情報処理" 共立出版, 294 (1993)

Masao Iri 等：“计算几何与地理信息处理”Kyoritsu Shuppan，294 (1993)

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

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

N.Kunihiro, K.Hayami and M.Sugihara: "Automatic numerical integration of nearly singular boundary element integrals." Lecture Notes in Num.Appl.Anal.Vol.14. 249-252

N.Kunihiro、K.Hayami 和 M.Sugihara：“近奇异边界元积分的自动数值积分。”

室田一雄(編): "離散構造アルゴリズムIII" 近代科学社, 204 (1994)

Kazuo Murota（主编）：《离散结构算法 III》Kindai Kagakusha，204（1994）