Design of numerically robust geometric algorithms

本课题组针对数值鲁棒几何算法提出的“组合抽象”设计原理，从理论和实验两方面进行了研究。该原理成功地应用于二维和三维空间中构造普通Voronoi图、构造线段和多边形的广义Voronoi图、构造三维凸壳、相交凸多面体、构造拉格尔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.