Construction of a Topology-Oriented Geometric System

点击翻译按钮获取中文摘要

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.