Design of numerically robust geometric algorithms

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

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.