Numerical Stabilization of Geometric Algorithms and Its Applications

几何算法的数值稳定性及其应用

基本信息

批准号：
01550279
负责人：
IMAI Toshiyuki
金额：
$ 1.54万
依托单位：
University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1989
资助国家：
日本
起止时间：
1989 至 1991
项目状态：
已结题

项目摘要

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

通常，已经设计了几何算法是基于以下假设：数值错误不会发生，因此，在不可避免的数值错误的情况下，它们不一定在实际计算中有效。我们搜索了一种设计几何算法的方法，该方法在数值错误上具有鲁棒性，并建立了一种新的设计方法，其中将最高优先级放在几何对象的拓扑一致性上，数值结果用作低优先级信息。因此，因此设计的算法并没有遇到不一致，因此执行其任务，从而使一些至少在拓扑上保持一致的输出。 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图，（5）提取线段的交叉点，（6）构造点的三维凸凸，（（7）简单多边形的固定理论操作，（8）convex polyhedra的交汇处，以及（9）laguerre vorerre vorerre vorerre voremoi diamomgram diamomgrams in nimage。特别是，针对问题（1） - （5）的新算法被实施到计算机程序中，并更正了计算实验。实验表明，无论计算的精度多么差，程序都不会失败，随着精度变得更高，新算法达到了真正的解决方案，即新算法实现鲁棒性，而无需增加常规算法实现的时间复杂性，而传统算法也很简单，因为新算法也很简单，因为对不成熟的方法进行了不合时宜的方法。快速自动分化方法用于获得数值误差的紧密结合，该方法应用于许多问题，例如基于Voronoi图的地理优化。还构建了一种追踪Abgebraic曲线的新方法，该方法可以在合理的时间内追踪全局和微型结构。我们还可以提高程序的性能（1） - （5）数值计算方式。较少的