Construction of a Topology-Oriented Geometric System

将面向拓扑的几何算法设计方法应用于计算几何中的基本问题。特别是今年，开发了数值稳定的软件，用于增量构造多边形的Voronoi图，用于多边形间的Minkowski运算，以及用于分而治之地构造三维凸壳。其中一些软件和以前开发的其他软件的手册也被构造出来。面向拓扑的算法解决了组合几何世界中的一个几何问题，因此输出不一定与欧几里德几何一致。从理论和实验两个角度分析了正确答案与输出之间的距离，并考虑了面向拓扑的算法的应用。将带数值扰动的Delaunay网格方法应用于有限元分析，提出了一种新的有限元分析方法。该格式是实用的，即使在Delaunay网格不完整的情况下也能稳定地工作。

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.