Numerical Stabilization of Geometric Algorithms and Its Applications

传统上，几何算法是在不发生数值误差的假设下设计的，因此它们在数值误差不可避免的实际计算中不一定有效。我们探索了一种对数值误差具有健壮性的几何算法的设计方法，并建立了一种新的设计方法，其中最优先考虑的是几何对象的拓扑一致性，而数值结果作为次要信息。这样设计的算法不会遇到不一致的情况，因此执行其任务，提供一些至少在拓扑上一致的输出。该设计方法被应用于设计健壮性算法：(1)点的二维Voronoi图的增量构造，(2)点的二维Voronoi图的分而治之的构造，(3)li…的二维Voronoi图的增量构造(4)点的三维Voronoi图的增量构造；(5)直线段交集的提取；(6)点的三维凸壳的构造；(7)简单多边形的集合论运算；(8)凸多面体的相交；(9)平面上Laguerre Voronoi图的构造。特别是，将问题(1)-(5)的新算法实现到计算机程序中，并进行了计算实验。实验表明，无论计算精度如何差，程序都不会失败，随着计算精度的提高，输出收敛到真实解，新算法在不增加传统算法的时间复杂度的情况下实现了鲁棒性，并且新算法简单，因为不需要对退化情况进行例外处理。利用快速自动微分法得到数值误差的紧致界，并将该方法应用于基于Voronoi图的地理优化等问题。提出了一种新的曲线跟踪方法，可以在合理的时间内同时跟踪全局构造和微观构造。我们还可以通过调整数值计算的方法来提高问题(1)-(5)的程序的性能。较少

Conventionally, geometric algorithms have been designed on the assumption that numerical errors do not take place, and consequently they are not necessarily valid in real computation where numerical errors are inevitable. We searched for a method for designing geometric algorithms that are robust against numerical errors, and established a new design methodology in which the highest priority is placed on the topological consistency of geometric objects and numerical results are used as lower-priority information. Algorithms thus designed does not come across inconsistency and hence carries out its task, giving some output that is at least topologically consistent. This design methodology was applied to design robust algorithms for the problems : (1) the incremental construction of two-dimensional Voronoi diagrams for points, (2) the divide-and-conquer construction of two-dimensional Voronoi diagrams for points, (3) the incremental construction of two-dimensional Voronoi diagrams for li … More ne segments, (4) the incremental construction of three-dimensional Voronoi diagrams for points, (5) the extraction of intersections of line segments, (6) the construction of three-dimensional convex hulls of points, (7) the set-theoretic operations of simple polygons, (8) the intersection of convex polyhedra, and (9) the construction of Laguerre Voronoi diagrams in the plane. In particular, the new algorithms for the problems (1)-(5) were implemented into computer programs, and computational experiments were corried out. The experiments show that, no matter how poor the precision in computation may be, the programs do not fail, that the outputs converge to the true solutions as the precision becomes higher, that the new algorithms achieve robustness without increasing time complexity achieved by conventional algorithms, and that the new algorithms are simple because exceptional processing for degenerate cases is not necessary.We also investigated numerical methods required in geometric algorithms. The fast automatic differentiation method were used to obtain the tight bound of numerical errors, and the method was applied to many problems such as geographic optimization based on Voronoi diagrams. A new method for tracing abgebraic curves was also constructed, which can trace both global and micro structures in reasonable time. We could also improve the performance of the programs for the problems (1)-(5) bytuning the ways of numerical computations. Less